数据结构测验题

1、华南农业大学期末考试试卷（A卷）2011-2012学年第1学期考试科目： 数据结构考试类型：（闭卷）考试考试时间：120 分钟学号姓名年级专业题号-一一-二二-三四总分得分评阅人考生须知:1. 答案必须写在“答卷”上，写在试卷上不得分；2. 考试结束时，只回收答题卡，不回收试卷；3. 必须在答题卡上正确填写班级、学号、姓名等内容，否则没有考试成绩。得分、选择题（本大题共10小题，每小题2分，共20分）1、以下数据结构中，哪一个是线性结构？（）A .广义表B .二叉树C .稀疏矩阵D .串2、 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为()(1<=

2、i<=n+1)。2A . 0(0)B. 0(1)C. 0(n)D. 0(n)3、 输入序列为 ABC，输出序列为BCA时，经过的栈操作为()。A . push, pop, push, pop, push, popB. push, push, pop, push, pop, popC. push, push, pop, pop, push, popD . push, pop, push, push, pop, pop4、 模式串t= abcaabbcabcaabdab该模式串的 next数组的值为()。A . 0 1 1 1 2 2 1 1 1 2 3 4 5 6 7 1 2B . 0 1

3、 1 1 2 1 2 1 1 2 3 4 5 6 1 1 2C . 0 1 1 1 0 0 1 3 1 0 1 1 0 0 7 0 1D . 0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 25、 设S为一个长度为n的字符串，其中的字符各不相同，则S中的互异的非平凡子串(非空且不同于S本身的串)的个数为()。2 2 2A . (n /2)+(n/2)-1 B . (n /2)+(n/2) C . n D . 2n-16、 假设以行序为主序存储二维数组A=array0.99，0.99，设每个数据元素占2个存储单元，基地址为10,则A5，5=（）。A. 808B. 818C. 10

4、10D. 10207、某二叉树中序序列为 A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E，则前序序列是：（）。A . E,G,F,A,C,D,B B . E,A,C,B,D,G ,F C . E,A,G,C,F,B,D D .上面的都不对&根据使用频率为 5个字符设计的哈夫曼编码不可能是（）。A. 0, 100, 101, 110, 111B. 0000, 0001, 001, 01, 1C. 000, 001, 010, 011, 11D. 00, 01, 10, 110, 1119、 采用分块查找时，若线性表中共有1225个元素，查找每个元素的概率相同，假设采用顺

5、序查找来确定结点所在的块时，每块应分（）个结点最佳。A. 15B. 25C. 35D. 31310、以下序列不是堆的是（）。A . （100,85,98,77,80,60,82,40,20,10,66）B. （100,98,85,82,80,77,66,60,40,20,10）C. （10,20,40,60,66,77,80,82,85,98,100）D. （100,85,40,77,80,60,66,98,82,10,20）得分二、应用 题（本大题共5小题，每小题6分，共30分）1、假设一棵二叉树的层次次序（按层次递增顺序排列，同一层次自左向右）为ABECFGDHI，中序序列为 BCDAFE

6、HIG。请画出该二叉树。2、举例说明顺序队的“假溢出”现象，简要叙述循环队列的数据结构，并说明判定循环队列的队空条件和队满条件。3、已知下列字符A、B、C、D、E、F、G的权值分别为3、12、7、4、2、8, 11,试填写出其对应哈夫曼树HT的存储结构的初态（见下表左半部分）和终态（见下表右半部分）（注意：生成的哈夫曼树权值左孩子小右孩子大，权值相等时编号小的先取）字符weightPare ntIchrch字符weightPare ntlchrch1122334、关键字序列为19,14,23,1,68,20,84,27,55,11,10,79，哈希函数为 H（key） = key mod 13

7、 ,采用链地址法处理冲突，给定哈希表的长度为13 （0-12）,要求画出关键字序列在哈希表中的存储状态，并计算在等概率情况下，查找成功的平均查找长度。5、给出一组关键字T=（12,2,16,30,8,28,4,10,20,6,18），写出用下列算法从小到大排序时第一 趟结束时的序列。（1）希尔排序（第一趟排序的增量为5）;（2）快速排序（选第一个记录为枢轴（分隔） ）。得分三、程序填空题(本大题共5小题，共15个空白处，每空2分，共30分, 注意：每空只填一个语句)1、 对不带头结点的单链表进行就地逆置。该算法用L返回逆置后的链表的头指针。voidreverse(li nklist &

8、L)p=null ； q=L ； while(q ！ =nuII) (1) ; /暂存后继q_>next=p ;p=q ；(2) ; /待逆置结点;/头指针仍为L2、 Search_Bin函数，实现在一个递增有序数组ST中采用折半查找法确定元素位置的算法。int Search_Bin(int *ST,int n,int key)在有序表ST中折半查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为-1。n为有序表的长度。int low,high,mid;low = 1;/置区间初值high = n;while( )mid = (low + high)/2 ; i

9、f ( .) return mid;else if (key < STmid)(6)_;elselow = mid + 1;return -1;/顺序表中不存在待查元素3、 下列算法为奇偶交换排序， 思路如下：第一趟对所有奇数的i，将ai和ai+1进行比较, 第二趟对所有偶数的i，将ai和ai+1进行比较，每次比较时若ai>ai+1，将二者交换；以后重复上述二趟过程，直至整个数组有序(从小到大)。注意：待排序的元素存储在数组下标1n的位置。void oesort (int an)int flag,i,t;doflag=0;for(i=1; i<n; i+=2)if(ai>

10、;ai+1)flag=1;t=ai+1;ai+1=ai;(7);for(8)if (ai>ai+1)flag=1t=ai+1;ai+1=ai;ai=t;while (9);4、图的广度优先遍历void BFSTraverse(Graph G , Status (*Visit)(int v ) 按广度优先非递归遍历图G。使用辅助队列Q和访问标志数组 visited，数组元素的值设为FALSE表示对应该结点未访问，设为TRUE则为已经访问。QElemType v,w;Queue Q;QElemType u;for (v=0; v<G.vex num; +v) visitedv =(10

11、);InitQueue(Q);/置空的辅助队列 Qfor (v=0; v<G.vex num; +v)if (!visitedv) visitedv = TRUE; Visit(v);rnx ;while (!QueueEmpty(Q) ;for (w=FirstAdjVex(G , u);w>=0; w=NextAdjVex(G , u, w)/ FirstAdjVex(G, u)取结点u的第一个相邻结点，NextAdjVex(G , u, w)取u的下一个/相邻结点if (13) visitedw = TRUE; Visit(w);En Queue(Q, w);/if/whil

12、e/if / BFSTraverse其中队列Queue数据结构的基本操作如下：Ini tQueue(Queue & Q);/ 构造一个空队列 QQueueEmpty(Queue Q);/若Q为空队列返回 TRUE，否则返回 FALSEQueueLength(Queue Q);/返回队列Q的元素个数EnQueue(Queue &Q, QElemType e);/插入元素e作为队列Q的队尾元素DeQueue(Queue &Q, QElemType &e);/删除队列Q的队头元素，并用 e返回其值假定上述操作已经实现，直接调用即可。请填空使之完善。二叉树链表的结点类5

13、、以下程序是二叉链表树中序遍历的非递归算法, 型的定义如下：typedef struct nodechar data; struct void vst(bitree bt) bitree p; p=bt;/C语言描述node *lchild,*rchild;*bitree;/bt为根结点的指针/初始化栈s为空栈/栈s不为空ini tstack(s);while(p | !empty(s)if(p) push (s,p);(14/p入栈沿左子树向下/栈顶元素出栈else p=pop(s);printf(“ c”a|ta);05.;得分四、算法设计题(本大题共2小题，每小题10分，共20分。请先简要说明 算法思想，然后写出算法的源代码实现)1、给定(已生成)一个带表头结点的单链表，设head为头指针，结点的结构为(data, next)，试写出算法：按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间。(要求：不允许使用数组作辅助空间)单链表定义如下：typedef struct LNodeintdata;struct LNode * n ext;LNode, * Li nkList;统一使用如下函数名：void Mi niDelete(Li nkedListhead)2、已知一二叉树中结点的左右孩子为lchil