2012数据结构复习题.doc

网络工程2011级“数据结构”课程复习样题 选择题 1．从逻辑上可以把数据结构分成______。 A、存储结构和运行时结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 2．在长度为n的顺序表的第i (1≤i≤n)个位置上删除一个元素，需要移动元素次数为______。 A、 n-i+1 B、 n-i C、 i D、 i-1 3．单链表中，增加头结目的是为了 A、使单链表至少有一个结点 B标示表结点中首结点的位置 C方便的实现 D说明单链表是线性表的链式存储实现。? A、仅修改队头指针 ?? B、仅修改队尾指针 ?? C、队头和队尾指针都要修改?? D、队头和队尾指针都可能要修改 6．广义表L=((a), (b)) 进行GetTail(GetHead( L))操作结果是______。 A、 a B、 (a) C、( ) D、(b) 7．如果哈夫曼树T有n个结点，则T的叶子结点数为______。 A、 (n-1)/2 B、 n/2 C、 (n+1)/2 D、 (2n-1)/2 8．若无向网G有n个顶点，e条边，克鲁斯卡尔算法的时间复杂度是______，因而适合于求边______的网的最小生成树。 A、 O(n2)， 稠密 B、 O(eloge)， 稠密 C、 O(n2)， 稀疏 D、 O(eloge)， 稀疏 9．以下关于折半查找算法的说法正确的是______。 A、可以使用顺序存储，也可以使用链式存储。 B、被查找的关键字序列必须有序。 C、可以用于查找任意的关键字序列。 D、 折半查找的效率低于顺序查找。 10．下面给出的四种排序法中______排序法是不稳定性排序法。 A、直接插入 B、冒泡 C、二路归并 D、堆排序 填空题 1．抽象数据类型的三个组成部分分别是：数据对象，_________，基本操作。 2．在带头结点的单链表L中，指针p所指结点是第一个结点的条件是_________。 3．在线性表的单链表存储结构中，每个结点包含两个域，一个叫数据域，另一个叫_________域。 4．具有先进先出特点的数据结构是 _________。 5．二维数组A[10][20]采用列为主序方式存储，每个元素占一个存储单元，并且A[0][0]的存储地址是200，则A[6][12]的地址是_________。 6．已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点。则该树含有的度为k的结点的数目为______。 7．如果哈夫曼树T有n个结点，则T的叶子节点数为 ______。 8．图的广度优先有哪些信誉好的足球投注网站遍历是树的______遍历的推广。 9．平衡二叉树上所有结点的平衡因子可能的取值有：__________。 10．邻接表和邻接矩阵两种存储结构中，较适合稠密图的是_________。 解答题 1．已知一个3×4的矩阵A转置后的三元组表示如下： i j e 1 1 3 1 3 2 2 2 -1 4 1 5 假设三元组的行号和列号都是从1开始，试写出该矩阵A。 2．某二叉树结点的中序序列为ABCDEFG，后序序列为BDCAFGE。 (1) 画出对应的二叉树；(4分) (2) 画出对应的森林。(4分) 3．已知某系统在通信中只使用八种字符，其频率分别为A(0.05), B(0.30), C(0.07), D(0.09), E(0.12), F(0.23), G(0.03), H(0.11)。 (1) 请以上述频度为权值构造哈夫曼树(要求树中所有结点的左孩子的权值小于右孩子的权值)； (2) 设哈夫曼树上左分支表示“0”，右分支表示“1”，请分别写出每个字符对应的二进制编码。 4、已知无向网G邻接矩阵存储结构如右图所示，回答下列问题： （1）根据下面给出的存储结构画出对应的有向网； （2）根据上面给出的存储结构，求从A出发广度优先有哪些信誉好的足球投注网站遍历序列； （3）给出该图的最小生成树。 5、将关键字序列：(19,14,1,29,20,23,57,11,10)，存入用数组A[0..12]实现的哈希表(见下表)，设哈希函数为：H0= key MOD 11，按线性探测再散列法处理冲突：Hi=(H0+di) MO