11
方式最节省时间。
A) 顺序表 B) 双链表
C) 带头结点的双循环链表 D) 单循环链表
10、若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。
A）(n-1)/2 B) n/2C) (n+1)/2 D) n
二、填空题（共15 空，每空 2 分，共 30 分）
1、数据的物理结构包括的表示和 的表示。
2、给定一组数据{6，2，7，10，3，12}以它构造一棵哈夫曼树，则树深度为__________，带权路径长度WPL的值为__________。
3、在单链表p结点之后删除s结点的操作是：______ 。
4、设有一批数据元素，为了最快地存取某元素，数据结构宜采用__________结构，为了方便地插入一个数据元素，数据结构宜采用__________结构。
5、在拓扑排序中，拓扑序列的第一个顶点必须是________的顶点。
6、对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是_____。 7、二叉树的第i层上最多含有结点数为 。 8、具有N个结点的二叉树，采用二叉链表存储，共有______个空链域。 9、一个有n（n>0）个结点的图，最少有个连通分量，最多有个连通分量。 10、对于具有N个结点的完全二叉树，其深度为 。
11、在长度为n的顺序表的第i个位置上插入一个元素（1≤ i ≤n+1），元素的移动次数为。
三、 算法题（共3题，每题5分，共15分） 1、请写一算法，求带有头结点的单向循环链表的表长。
2、请用非递归算法写出在二叉树中计算叶子结点个数的算法。
3、请写出简单选择排序的算法。
12
四、操作题（共6题，第1题10分，其余每题5分，共35分）
1、已知一组关键字为（19，14，23，01，68，20，84，27，55，11，10，79），则按哈希函数H(key)=key mod 13 和链地址法处理冲突构造哈希表。（10分）
2、请写出在如下具有11个数据元素的有序表中使用折半查找算法查找21的过程（关键字即为数据元素的值）。（5分）
（05， 13，19，21，37，56，64，75，80，88，92）
3、对于下面的有向图G，请写出所有可能的拓扑序列。（5分）
4、写出对数据（49，38，65，97，76，13，27，49）进行快速排序中第一趟的序列。（5分）
5、无向图G=(V，E)，其中：V={a，b，c，d，e，f},E={(a，b)，(a，e)，(a，c)，(b，e)，(c，f)，(f，d)，(e，d)}，写出对该图进行广度优先遍历的序列。（5分）
6、已知一棵二叉树前序为ABDEGCF，中序为DBGEACF，画出这棵二叉树。（5分）
套题5
一、选择题（每题2 分，共10题，总计20 分） 1．以下那一个术语与数据的存储结构无关？（） A．栈B. 哈希表C. 线索树D. 双向链表
2．对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（） A．head==NULL B．head→next== head C．head→next== NULL D．head!=NULL 3. 对于栈操作数据的原则是（）。 A. 先进先出B. 后进先出
C. 后进后出
D. 不分顺序
B A C E D 13
4．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（） A．9
B．11
C．15
D．不确定
5．树的后根遍历序列等同于该树对应的二叉树的( ). A. 先序序列 B. 中序序列C. 后序序列D．不一定 6．n个结点的完全有向图含有边的数目（ ）。 A．n*n B．n（n＋１） C．n／2 D．n*（n－l） 7．下列哪一种图的邻接矩阵是对称矩阵？（） A．有向图
B．无向图C．AOV网D．AOE网
8. 下面关于哈希(Hash，杂凑)查找的说法正确的是( ) A．哈希函数构造的越复杂越好，因为这样随机性好，冲突小 B．除留余数法是所有哈希函数中最好的 C．不存在特别好与坏的哈希函数，要视情况而定
D．若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可 9．下列排序算法中，其中（）是稳定的。 A. 堆排序，冒泡排序B. 快速排序，堆排序
C. 直接选择排序，归并排序D. 归并排序，冒泡排序
10堆是一种有用的数据结构。试判断下面的关键码序列中哪一个是堆( ) A．16，72，31，23，94，53 B．94，53，31，72，16，23 C．16，53，23，94，31，72 D．16，31，23，94，53，72
二、填空题（每空2 分，共20空，总计40 分）
1．在下面的程序段中，语句x+=1的频度是___________________，语句A[i][j]=1的频度是________________，整个程序的时间复杂度是___________________。 for(i=0;i 2．在单链表指针为p的结点之后插入指针为s的结点，操作是__________________， 14 _______________________。 3．从逻辑上可以把数据结构分为_____和两大类。 4．一个队列的输入顺序是a，b，c，d，e，则其输出序列为________________________。 5．一个具有N个顶点，K条边的无向图是一个森林（N > K），则该森林必有_____棵树。 6．构造连通网最小生成树的两个典型算法是__________________和________________________。 7．设G是一个非连通无向图，共有28条边，则该图至少有______个顶点。 8．若 (u, v) 是 E(G) 中的一条边，则称 u 与 v 互为__________。 9．一棵具有20个结点的完全二叉树的树高度（深度）是。 10．具有10个叶结点的二叉树中有个度为2的结点。 11．有3个结点的二叉树将会呈现种不同的表现形式。 12．N个顶点的连通图的生成树含有______条边。 13．具有N个结点的二叉树，采用二叉链表存储，共有个空链域。 14．二叉树中某一结点左子树的深度减去右子树的深度称为该结点的。 15．有一个长度为12的有序表，按二分查找法对该表进行查找，且查找每个元素的概率相同，则查找成功所需的平均查找长度为。 三、算法题（每题8分，共2题，总计16分） 1关键字序列a,b,c，d的链式存储如下，编写算法删除d所在的结点，是删除之后的新序列为{a，b，e}。 其中结点定义为： struct node{ char data; struct node * next; }; 2、①请写出快速排序的算法。（5分） ②对{503，87，512，61，908，170，897，275，653，462}，以第一个记录为枢轴，写出按升序进行一趟快速排序的结果。（3分） head a b c d ∧ 15 得分 阅卷人 四、操作题（每题6分，共4题，总计24分） 1、已知某栈结构定义如下，现有一字符序列以{a，b，c，d}的顺序进栈,试完成下 面的操作，使最终的输出序列为{a，c，b，d} struct stack{ int base; int top; stactsize N;/*N>4*/ }; main（）{ Init (stack); Push (a); ; ; ; Pop; /*栈顶元素c出栈*/ ； Push (d); Pop; }/*end of main*/ 2、假设一棵二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。 ①请画出该二叉树。(4分) ②将此二叉树转化成其对应的森林。（2分） 3、无向图G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)} ①请画出该图，并给出该图的邻接矩阵表示(4分) ②依据你所作的邻接矩阵，从A出发，给出该图的深度优先遍历序列（2分） top base