《数据结构》复习资料及答案.doc

江苏广播电视大学高等专科教育2008年一次性考试
《数据结构》复习资料及答案
　　一、单选题（每小题2分，共8分）
　　1. 在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行________。
　　　　A HL=p; p->next=HL; B p->next=HL; HL=p;
　　　　C p->next=HL; p=HL; D p->next=HL->next; HL->next=p;
　　2. 在一个顺序队列中，队首指针指向队首元素的________位置。
　　　　A 前一个 B 后一个 C 当前
　　3. 从二叉搜索树中查找一个元素时，其时间复杂度大致为________。
　　　　A O(n) B O(1) C O(log2n) D O(n2)
　　4. 由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为________。
A 24 B 48 C 72 D 53
5. 一个数组元素a[i]与________的表示等价。
A *(a+i) B a+i C *a+i D &a+i
6. 下面程序段的时间复杂度为____________。C
for(int i=0; i<m; i++)
for(int j=0; j<n; j++)
a[i][j]=i*j;
A O(m2) B O(n2) C O(m*n) D O(m+n)
　　二、填空题（每空1分，共32分）
　　1. 一个算法的时间复杂度为(3n2+2nlog2n+4n-7)/(5n)，其数量级表示为________。
　　2. 在以HL为表头指针的带表头附加结点的单链表和循环单链表中，链表为空的条件分别为________和________。
　　3．一个广义表中的元素分为________元素和________元素两类。
　　4．从一个链栈中删除一个结点时，需要把栈顶结点的_________域的值赋给________。
　　5．在进行函数调用时，需要把每个实参的值和调用后的________传送给被调用的函数中。
　　6．对于一棵具有n个结点的二叉树，若一个结点的编号为i(1≤i≤n)，则它的左孩子结点的编号为________，右孩子结点的编号为________，双亲结点的编号为________。
　　7．在一棵高度为5的理想平衡树中，最少含有________个结点，最多含有________个结点。
　　8．在一个堆的顺序存储中，若一个元素的下标为i(0≤i≤n-1)，则它的左孩子元素的下标为______，右孩子元素的下标为________。
　　9．在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有向完全图中，包含有________条边。
　　10．对于一个具有n个顶点和e条边的有向图和无向图，若采用边集数组表示，则存于数组中的边数分别为________和________条。
11．以二分查找方法从长度为20的有序表中查找一个元素时，平均查找长度为________。
12．假定一个线性表为(12,23,74,55,63,40,82,36)，若按Key % 3条件进行划分，使得同一余数的元素成为一个子表，则得到的三个子表分别为_____________、_____________和_____________。
　　13．在线性表的散列存储中，装填因子a又称为装填系数，若用m表示散列表的长度，n表示待散列存储的元素的个数，则a等于________。
　　14．在一棵m阶B_树上，每个非树根结点的关键字数目最少为________个，最多为________个，其子树数目最少为________，最多为________。
　　15．在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为________，整个堆排序过程的时间复杂度为________。
16. 快速排序在平均情况下的时间复杂度为________，在最坏情况下的时间复杂度为________。
17. 数据的存储结构被分为____________、___________、____________和
____________四种。
18. 在线性结构、树形结构和图形结构中，前驱和后继结点之间分别存在着________、
________和________的联系。
19．一棵深度为5的满二叉树中的结点数为________个，一棵深度为3的满四叉树中的结点数为________个。
20．假定一棵树的广义表表示为A(B(C,D(E,F,G),H(I,J)))，则树中所含的结点数为________个，树的深度为________，树的度为________。
21．假定一棵树的广义表表示为A(B(C,D(E,F,G),H(I,J)))，则度为3、2、1、0的结点数分别为______、______、______和______个。
22. 假定一棵树的广义表表示为A(B(C,D(E,F,G),H(I,J)))，则结点H的双亲结点为________，孩子结点为___________。
23．在一棵二叉树中，假定双分支结点数为5个，单分支结点数为6个，则叶子结点数为________个。
24．在一个图中，所有顶点的度数之和等于所有边数的________倍。
25. 在一个具有n个顶点的无向图中，要连通所有顶点则至少需要________条边。
26．表示图的三种存储结构为________、________和________。
27．对于二分查找所对应的判定树，它既是一棵_______，又是一棵________。
28．假定对长度n=50的有序表进行二分查找，则对应的判定树高度为________，判定树中前5层的结点数为________，最后一层的结点数为________。
29．在索引表中，每个索引项至少包含有________域和________域这两项。

　　三、运算题（每小题6分，共24分）
　　1. 假定一棵二叉树广义表表示为a(b(c),d(e,f))，分别写出对它进行先序、中序、后序、按层遍历的结果。
　　　　先序：
　　　　中序：
　　　　后序：
　　　　按层：
　　2．已知一个图的顶点集V和边集G分别为：V={0,1,2,3,4,5,6,7};
　　　　E={(0,1)8,(0,2)5,(0,3)2,(1,5)6,(2,3)25,(2,4)13,(3,5)9,(3,6)10,
　　　　　(4,6)4,(5,7)20,(6,7)30};
　　按照普里姆算法从顶点0出发得到最小生成树，试写出在生成最小生成树的过程中依次得到的各条边。
　　　　________, ________, ________, ________, ________, ________, ________。
3. 已知一个图的顶点集V和边集G分别为：
　　　　V={0,1,2,3,4,5,6,7,8};
　　　　E={<0,2>,<1,3>,<1,4>,<2,4>,<2,5>,<3,6>,<3,7>,<4,7>,<4,8>,
　　　　　<5,7>,<6,7>,<7,8>};
　　若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，则按主教材中介绍的进行拓扑排序的算法，写出得到的拓扑序列（提示：先画出对应的图形，然后再运算）。
　　拓扑序列：
4. 假定一组记录的排序码为(46,79,56,38,40,80,25,34)，则对其进行快速排序的第一次划分后的结果为________________。
5、假定一个待散列存储的线性表为(32,75,29,63,48,94,25,46,18,70)，散列地址空间为HT[13]，若采用除留余数法构造散列函数和线性探查法处理冲突，试求出每一元素的散列地址，画出最后得到的散列表，求出平均查找长度。
　　四、阅读算法，回答问题（每小题8分，共16分）

　　该算法被调用后得到的输出结果为：

　　该算法的功能为：
　　　　______________________________________________________________。
　　五、算法填空，在画有横线的地方填写合适的内容(10分)。

　　六、编写算法(10分)
　　编写向类型为List的线性表L中第i个元素位置插入一个元素的算法，假定不需要对i的值进行有效性检查，同时不需要检查存储空间是否用完。
void Insert(List& L, int i, ElemType x)

参考解答
　　一、单选题（每小题2分，共8分）
　　1. B 2. A 3. C 4. D 5.A 6.C
　　二、填空题（每空1分，共32分）
　　1. O(n)
　　2. HL->next==NULL HL->next==HL
　　3. 单、 表
　　4. 指针 、栈顶指针
　　5. 返回地址
　　6. 2i、 2i+1、 i/2
　　7. 16 、31
　　8. 2i+1 、2i+2
　　9. n(n-1)/2、 n(n-1)
　　10. e 、e
　　11. 37/10
　　12. （12,63,36）、 (55,40,82) 、(23,74)
　　13. n/m
　　14. m/2-1、 m-1、 m/2、 m
　　15. O(log2n) 、O(nlog2n)
16. O(nlog2n) O(n2)
17、顺序、链接、索引、散列
18、1对1、1对多、多对多
19、31、 21
20、10、 4、 3
21、2、 1 、1、 6
22、B 、I和J
23、6
24、2
25、n-1
26、邻接矩阵 邻接表 边集数组
27、二叉树、理想平衡树
28．6 31 19
29．索引值 子表开始域

　　三、运算题（每小题6分，共24分）
　　1. 先序： a,b,c,d,e,f
　　　　中序： c,b,a,e,d,f
　　　　后序： c,b,e,f,d,a
　　　　按层： a,b,d,c,e,f
　　2. (0,3)2, (0,2)5, (0,1)8, (1,5)6, (3,6)10, (6,4)4, (5,7)20
　　3. 拓扑序列：1,3,6,0,2,5,4,7,8
4. [40 34 25 38] 46 [80 56 79]
5、每一元素的散列地址为：
h(32)=32%13=6 h(75)=75%13=10 h(29)=29%13=3
h(63)=63%13=11 h(48)=48%13=9 h(94)=94%13=3 冲突
h1(94)=h(94)+1=4 h(25)=25%13=12 h(46)=46%13=7
h(18)=18%13=5 h(70)=70%13=5 冲突 h1(70)=h(70)+1=6 冲突
h2(70)=7 冲突 h3(70)=8
平均查找长度ASL=(8+2+4)/10=1.4
散列表Ht[13]为：
0 1 2 3 4 5 6 7 8 9 10 11 12

29
94
18
32
46
70
48
75
63
25

　　四、阅读算法，回答问题（每小题8分，共16分）
　　1. 15 12 8 5 130 30
　　2. 从初始点vi出发广度优先搜索由邻接表GL所表示的图。
　　五、算法填空，在画有横线的地方填写合适的内容(10分)。
　　BST->left=BST->right=NULL
　　Insert(BST->left, item)
　　Insert(BST->right, item)
　　六、编写算法(10分)