C.限制在链表头p进行D.限制在链表尾p进行
5. 串函数strcmp(“bcde”,”Bcde”)的返回值是
A.小于0 B.等于0 C.大于0 D. –1
6.广义表（（））的长度为
A. 0 B. 1 C. 2 D.不确定
7.某二叉树的后序遍历序列为dabec,中序遍历序列为debac,则前序序列遍历为
第三套数据结构自测题
一、单项选择题(本大题共有15小题，每小题2分，共30分)
（在每小题列出的四个选项中只有一个选项符合题目要求，请将正确选项前的字母填在题后的括号内。）
1.数据在计算机存储器内表示时，根据结点的关键字直接计算出该结点的存储地址，这
种方法称为
A.索引存储方法B.顺序存储方法C.链式存储方法D.散列存储方法
19. 在上三角矩阵中，它的_______中的元素均为常数C。上三角矩阵中的重复元素C
可共享一个存储空间，其余的元素正好有________个（设上三角矩阵的阶数为n）。
20. 高度为n的完全二叉数最多有________个结点；最少有________个结点。
21. 对于一棵有n个结点的4度数，每个结点中有4个指针，指向子结点，则树中指向子
tp
原子结点：
Tag=0
atom
其C语言描述如下：
typedef enum{ATOM,LIST}ElemTag;
typedef struct GLNode{
ElemTag tag; //公共部分，用语区分原子和表
union{ //原子结点和表结点的联合部分
DATA atom; //atom是原子结点的值域
#define max 100
typedef struct tnode {
elemtype data;
struct tnode * lchild,* rchild;
}tnode;
typedef struct stack{
tnode * elem[max];
int top;
}stack;
void inorder(tnode * bt)
#define error –1
#defing ok 1
int substing{Hstring&sub,Hstring S, int pos,int length}
{
if(pos<1||pos>s.legth||len<0||__(1)______)
return error;
if(sub.ch) free(sub.ch);
30.从一个空的二叉排序树开始，将以下关键字25，13，15，34，7，20，37依次插入，请画出全部插入后的二叉排序树。
四、读程序填空题（本大题共4小题，每小题5分，共20分）
31.设串的堆存储可用C描述为typedef struct{char* ch;int legth;试填写以
它为基础的求子串程序。
16. 顺序表的存储密度为________，而链表的存储密度为________。
17. 在有n个元素的链队列中，入队和出队操作的时间复杂度为_______和_______。
18. 在串运算中，strcmp(“abc”,”abef”)的值_______;顺序串上的串定位运算NaiveStr-Match(“acaabc”,”aab”)的值为_______。
Struct{
Struct GLNode *hp, *tp;
}ptr; //ptr是表结点的指针域，
//ptr.hp指向表头，ptr.tp指向表尾
}
}*Glist;
试填写一下求表深度的递归算法。
Int GlistDepth(Glist L)
{
int dep;
if(!L) return__(1)________;
R填入表H中的算法。
}
}while(!(s.top—1&&s.elem[s.top—1]= =null));
______(5)___;
}
34.下列算法的功能是求出指定结点在给定的二叉排序树中所在的层次。请完善该算法。
Void leve1(BSTree root,p)
{
int leve = o;
if (!root)
___(1)______;
24. 希尔排序属于_________排序方法；堆排序属于_________排序方法。
25. 在插入和选择排序中，若初始数据基本正序，则选用________；若初始数据基本反
序，则选用________。
三简答题（本大题共5小题，每小题4分，共20分）
26. 顺序队列中的假上溢用什么方法解决？请作简短的解释。
A.n B.(n-1)2C.n+1 D.n2
11.下述几种排序方法中，要求内存量最大的是
A.插入排序B.快速排序C.归并排序D.选择排序
12. 对n个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数为
A.n+1 B.n C.n-1 D.n(n-1)/2
13.对线性表示进行二分查找时，要求线性表必须
结点的指针有________个，空指针有_________个。
22. 某二叉树的前序遍历序列为IJKIMNO,中序遍历序列为JLKNMO,则后序遍历序列
为_________。由一棵二叉树的后序序列和_________可惟一确定这棵二叉树。
23. 堆排序的时间复杂度为________；辅助存储空间为__________。
if(__(2)________) return____________;
for(max=0,pp=L;__(3)________;pp=pp-- >ptr.tp)
{
dep=__(4)________;
if(dep>max)___(5)_________;
}
return max+1;
}
33.完成下列中序列遍历二叉的算法。注意，在遍历中只用一个栈，而不用任何其他变量。
2.在单链表中，存储每个结点需要有两个域，一个是数据域，另一个是指针域，它指向该结点的
A.直接前趋B.直要在其尾部插入一新结点，其算法所需要的时间复杂度为
A.O(1) B.(lgn) C.(n) D.O(n2)
4.在链接队列执行入队操作，
A.需判断别队是否空B.需判断别队是否满
if(!length)
{
=__(2)_______;/sub.length=0;
}
else
{
sub.ch=__(3)________;
sub.ch[0..length—1]=___(4)__________;
}
return ok;
}
32.设广义表采用如下存储结构：
表结点为：
Tag=1
hp
A.以顺序方式存储
B.以链接方式存储
C.以顺序方式存储，且结点按关键字有序排列
D.以链接方式存储，且结点按关键字有序排列
14. 下列方法中，不稳定的排序是
A.直接插入排序B.冒泡排序C.堆排序D.归并排序
15. 在索引非顺序文件中，建立的索引表是
A.稠密索引B.稀疏索引C.多级索引D.链接索引
二、填空题（本大题共10小题，每小题2分，共20分）
A.acbed B.decab C.deabc D.cedba
8.含有n个结点的二叉树用二叉链表表示时，空链域个数为
A.n--1B.n C.n+1 D.n+2
9.在一个图中，所有顶点的度数之和与图的边数的比是
A.1:2 B.1:1 C.2:1 D.4:1
10.n个顶点的无向图若采用邻接矩阵存储，则该矩阵的大小是
36.设计一个折半查找算法，在一组字符串中找出给定的字符串，假设所有的字符串都
等长，并且由四个字母组成。（1）请写出算法；（2）分析该算法的最大查找长度。
37.设给定的散列存储空间为：H[O..m],每个H[i]单元可存放一记录，选取的散列函数
为H[R.key],其中R.key为记录关键字，解决冲突的方法为线性探测法，试编写将某记录
{ stack s;
s.top=0;__(1)________;
do
{while(___(_2)_____)
s.elem[s.top++]=s.elem[s.top—1]—1child
if(s.top>1)
{__(3)________;
printf(s.elem[s.top—1]=__(4)_____;
27. 试写出下列广义表运算的结果：tail(((a,b),(c,d))))。
28.分别画出满足下列条件的所有二叉树：
（1）前序序列和中序序列均为ABCDE;
（2）前序序列为ABCDE,并且与其对应的二叉树高度为5。
29.什么是堆？请写出对应于序列{10，20，7，75，41，67，3，9，30，45}的初始堆（堆顶元素取最小值）。
else{
leve1 ++;
while{(root-->key!=p-- >key){
if (root-- >key<p—key)
__(2)______;
else
______(3)__;
leve1 ++;
}
______(4)__;
}
}
五、程序设计题（本大题有3小题，可任选1题做，共10分。
35.编写算法判断以下二叉链表是否为二叉排序树。