11年数据结构试卷（无答案）
一选择
1、下列程序段的时间复杂度为（）。
k=0;
for(i=0; i<10; i++)
k++;
A．O(1) B．O(logn) C．O(n) D．O(n )
2、已知在一个单链表中，q 所指结点是 p 所指结点的前驱结点，若在 q 和 p 之间插入 s 结点，则执行语句（）。
A．s->next=p->next; p->next=s;
B. p->next=s->next; s->next=p;
C．q->next=s; s->next=p;
D. p->next=s; s->next=q;
3、若用一个长度为 6 的数组来实现循环队列，且当前 front 和 rear 的值分别为 4 和 1，则该队列的长度是（）。
A．2 B．3 C．4 D．6
4、稀疏矩阵的常用压缩方法有两种，即（
）。
A. 二维数组和三维数组
B. 三元组顺序表和散列表
C. 三元组顺序表和十字链表
D. 十字链表和散列表
5、在有向图的拓扑序列中，若顶点 a 在顶点 b 之前，则下列情形不可能出现的是（）。
A. G 中有弧<a, b>
B. G 中有一条从 a 到 b 的路径
C. G 中没有弧<a, b>
D. G 中有一条从 b 到 a 的路径
6、具有 35 个结点的完全二叉树的深度为（）。
A．5 B．6 C．7 D．8
7、在对查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到查找表中。
这种方式主要适合于（）。
A．动态查找表 B．静态查找表
C．静态查找表与动态查找表 D．静态查找表或动态查找表 8、二分查找要求被查找的表是（）。
A．键值有序的链表 B．链表但键值不一定有序
C．键值有序的顺序表 D．顺序表但键值不一定有序
9、若在排序中，从未排序序列中依次取出元素与已排序序列（初始为空）中的元素进行比较，将其放入已排序序列的正确位置，则该方法称为（）。
A．希尔排序 B．起泡排序
C．插入排序 D．选择排序
10、外部排序是指（）。
A．用机器指令直接对硬盘中需排序数据排序
B．把需排序数据用其他大容量机器排序
C．把外存中需排序数据一次性调入内存，排好序后，在输回外存
D．对外存中大于内存允许空间的需排序的数据，通过多次内外存的交换实现排序
二、填空题(10 分，每空 1 分)
1、数据元素及其关系在计算机存储器的表示，称为数据的 ( )。
2、对于长度为 n 的顺序表，假定删除表中任一元素的概率相同，则删除一个元素
平均需要移动元素的个数是 ( ) 。
3、用 S 表示入栈操作，X 表示出栈操作，若元素入栈的顺序为 1234，为了得到
1342 出栈顺序，用相应的 S 和 X 表示的操作串为 SX( ) 。
4、Index (S, T, pos)操作的功能是：从串 S 中第 pos 个字符起查找和串 T 值相同的子串，若找到，则返回其第一次出现的位置。
假设 S = ‘cbcaabca’,T = ‘bca’，则 Index(S, T, 1) = ( ) 。
5、广义表(a,((b),c))的深度是( ) 。
6、已知某二叉树有 31 个叶子结点，且仅有一个孩子的结点数为 40，则该树的结点总数为 ( ) 。
7、已知无向图 G={V, E}，其中 V = {a, b, c, d, e}，E={(a, b), (a, d), (a, c), (d, c), (b, e)}，如果从顶点 a 开始遍历图，遍历序列为 abcde，则采用的是遍历方法是（）。
8、在二叉排序树插入新结点时，新结点一定成为二叉排序树的（）结点。
9、若在排序中，从未排序序列中挑选元素，并将其依次放入已排序列（初始序列为空）的一端，则该排序方法被称为（）排序。
10、文件检索的三种方式是：顺序存取，（），按关键字存取
三、解答题
1、（7 分）二维数组 A[8][9]的元素都是 5 个字符组成的串，请回答下列问题：
（1）A 的第 6 列和第 4 行的所有元素共占多少个字节；
（2）若 A 按行存放，元素 A[6][4]的起始地址与 A 按列存放时哪一个元素的起始地址一致，并说明理由。
设存在第 0 行和第 0 列元素，即从元素 A[0][0]开始存放
2、（7 分）已知有向带权图 G 如图所示，试画出图 G 的逆邻接表，其中邻接链表中每个顶点按由
3、（7 分）画出与图中所示的二叉树等价的树
4、（7 分）设哈希函数为 H(k)=k MOD 7，用链地址法处理冲突。
请画出依次插入元素 29,38,24,71,63,52 后，该哈希表的状态。
5、（8 分）已知序列{503,87,512,61,908,170,897,275,653,462} （1）请判断该序列是否是大顶堆，并说明理由，若不是请调整为大顶堆。
（2）写出输出最大数 908 后，经调整后的大顶堆序列
四、算法填空（36 分，每题 6 分）
1、（6 分）算法 f1 求带头结点的单链表长度。
请在画线处填空。
2、（6 分）阅读算法 f2，回答下列问题：
（1）设队列 Q=(1,2,3,4,5,6)，请写出执行算法 f2(Q)后的队列 Q；
（2）简述算法 f2 的功能。
3、（6 分）如图所示的二叉树 T 采用二叉链表存储结构，1）请画出执行算法 f3(T)后的二叉树 T；
（2）简述算法 f3 的功能。
4、（6 分）图的逆邻接表存储结构的类型定义如下：
假设有向图 G 是用逆邻接表存储，算法 f4 计算有向图 G 中顶点 v 的入度。
请在画线处填空。
5、算法 f5 对 r[h],r[h+1],…. r[p]子序列进行一趟快速排序。
请在画线处填空。
6、（6 分）算法 f6 将键值为 x 的结点插入到二叉排序树中，请在画线处填空。
五、算法设计题（8 分）
一个线性表的冗余度为 n/m，其中 n 和 m 分别为表中元素总数和不同元素个数。
编写算法，求一个带头结点的有序单链表的冗余度。
例如，下表的冗余度为 17/9。
（1,2,2,3,4,4,4,5,5,6,6,6,6,7,8,9,9）
六、附加题（10 分，二选一，多做只按第一题给分）
1、某百货公司仓库中电视机的编码和数量信息，按其编码从小到大存储在一个带头结点的循环链表中。
链表的结点由编码、数量和链指针三个域组成
现新到 m 台编码为 c 的电视机需入库，试为此编写修改循环链表中存储的电视机信息的算法。
2、如果一棵二叉树中不存在度为 1 的结点，则称其为正则二叉树。
假设二叉树采用二叉链表存储结构，请编写一个正则二叉树的判定算法。
