06年转升本数据结构考题
一、 单项选择题（共12 小题，每小题2分,共24分） 1、已知单链表结构为 struct node{ int data;
struct node *next; }*p,*q,*r ;
删除单链表中结点p(由p指向的结点)后面的结点的操作不正确的是__C__ A、 q=p->next; p->next=q->next;
B、p->next=p->next->next;
C、r=p->next; p->next=q->next;
D、q=p->next; r=q->next; p->next=r;
2、若待排序对象序列在排序前已经按照关键字递增排列，则采用__A__比较次数最少。
A、直接插入排序 O(n) B、快速排序 O(n2) C、合并排序
D、简单选择排序 O(n2)
3、图的深度优先遍历类似于树的__C__ A、后序遍历 B、层次遍历 C、前序遍历 D、中序遍历
4、求赋权有向图的最短路径常用的算法有___D___
A、Prim算法和Kruskal算法 B、Prim算法和Dijkstra算法 C、Kruskal算法和Dijkstra算法 D、Dijkstra算法和Floyd算法
5、单链表中有n个结点，在其中查找值为x的结点，在查找成功时需要比较的平均次数是___D___。 A、n
B、(n-1)/2 C、n/2 D、(n+1)/2 解答：
查询每个元素需要比较次数之和 查询平均复杂度 = ----------------------------------------------
元素个数
1 + 2 + 3 +... +n n+1 = ---------------------------- = --------
n 2
思考：如果查找不成功，计算结果如何？
6、线性表采用链式存储时，结点的存储地址__B___ A、必须是不连续的 B、连续与否均可 C、必须是连续的
D、和头结点的存储地址项连续
7、一棵非空的二叉树中，设根结点在第0层，在第i层上最多有___D__个结点。 A、2(i+1) B、2i C、2(i-1) D、2i
根 层0 1个 / \\
A B 层1 2个
/ \\ / \\
A B C D 层2 4个
8、在下列的排序算法中，算法的时间复杂度是O(n*log2n)是___D__。 A、冒泡排序 B、简单选择排序 C、直接插入排序 D、堆排序
9、使用一个栈，每次限制进栈和出栈一个元素。假设进栈的元素序列依次是a、b、c、d；指出不可能的出栈序列___B____。 A、abcd B、adbc
C、acbd D、dcba 解答： A、 push(a)、pop()、push(b)、pop()、push(c)、pop()、push(d)、pop(), B、 没办法 C、 push(a)、pop()、push(b)、 push(c)、pop()、pop()、push(d)、pop() D、 push(a)、push(b)、push(c)、push(d)、pop()、pop()、pop()、pop()
10、设数组queue[]作为循环队列Q的存储空间，front作为队头指针，rear作为队尾指针，则执行出队操作后其头指针front的值为__A___。 A、front=(front+1)%m B、front=(front+1)%(m-1) C、front=(front-1)%m D、front=front+1
解答：与方案1、2无关。
11、对图进行广度优先遍历时，通常采用__C__来实现 A、字符串 B、B树 C、队列 E、 栈
12、一个有n个结点k叉树，树中所有结点的度数之和是__B__。 A、k+n B、n-1 C、kn D、n2 解答：
思路1：树中结点的度数=结点的儿子数 n个结点k叉树，每个结点最多有k个儿子，叶子没有儿子，因此答案不是k*n。 思路2：正确的做法：
树中所有结点的度数之和=树中所有边条数，
每一条边指向一个结点，每个结点有一条天线，指向父亲结点，除了根结点之外。故答案是B，n-1
二、 填空题（共8 小题，11空，每空2分,共22分）
13、已知二叉树后序列表为CEDBA，中序列表为CBEDA，则它的前序列表为__ABCDE__。
解答：后序列表为CEDBA，因此根是A，
中序列表为CBEDA，因此根只有左子树CBED，没有右子树
A /
CEDB后序，根是B
CBED中序，左子树C，右子树ED
A / B
/ \\
C ED后序
ED中序 A / B
/ \\
C D
/ E
14、N个结点的有向图，最多有___N*(N-1)_____条边。
15、存储图的最常用方法有两种，它们是___邻接矩阵____和____邻接表____。 16、设有一个闭散列表的容量为m，用线性探测法解决冲突，要插入一个键值，若插入成功，至多要进行______比较。
17、一棵哈夫曼树有29 个结点，其叶子的个数是___15____。 解答：哈夫曼树没有度为1的结点， 叶子数=内结点数+1 结点总数
=叶子数+内结点数 =2*叶子数-1 =2*内结点数+1
18、已知单链表的结点定义为 struct node{ int data;
struct node *next; };
在单链表中搜索结点p(由指向的结点)的后继结点的操作是____p=p->next___。 19、已知双链表结点定义为 struct node{ int data;
struct node *left,*right; };
双链表中结点的left和right分别指向前驱和后继结点，在双链表中删除结点p(由指向的结点)的操作是：p->left->right=___p->right______；和p->right->left=___p->left_____。
20、对于队列，只能在__队尾___插入元素，在___队头____删除元素。 三、 应用题（共4小题，每小题8分，共32分） 21、对图1所示的树
（1） 结点A的度是_____3______。 （2） 树的度是______3_____。
（3） 画出其转换成相应二叉树的树形 A
/ | \\ B C D
/ \\ / \\ E F G H /
I
解答：一般树转换成二叉树步骤：
将父亲管理儿子方式改为 父亲管理大儿子，
大儿子管理二儿子（二儿子变成大儿子的右孩子）
二儿子管理三儿子（三儿子变成二儿子的右孩子）
A ABEFCDGIH 前
/ EFBCIGHDA 中 B
/ \\ FEIHGDCBA后 E C \\ \\ F D
/ G / \\ I H
22、已知参加排序的正整数序列是：90、70、180、30、520、40、60、80、50、130。以第一个元素90作为基准元素，根据快速排序算法，写出完成第一趟划分后序列重新排列的情况。
60、70、50、30、80、40、90、520、180、130
23、一次输入如下序列中的各个整数，构造其相应的二叉搜索树，只需要画出最后生成的二叉搜索树的树形。整数序列是180、160、250、300、170、120、125、290、380。
180
/ \\ 160 250 / \\ \\ 120 170 300
\\ / \\
125 290 380
24、用Prim算法求图2所示的无向带权连通图的最小生成树。要求依次画出从顶点1出发的最小生成树的生成过程。
1 \\ 4 1 / \\ 2 3— 4 1 / \\ 2 4 1 / \\ 2 3— 4 / 5
四、 算法设计（共2小题，第25小题10分，第26小题12分，共22分） 25、二叉树以二叉表为存储结构，结点结构的定义如下，请写出一个求二叉树中叶子结点个数的算法。
typedef struct btnode *btlink; struct btnode{
TreeItem element; btlink left; btlink right; }Btnode
解答：与05年考题不一样
int f(指向树根的指针){//f()计算树中叶子节点的个数 if(指向树根的指针==NULL)return 0;
x=f(指向树根的左孩子指针); //左子树中叶节点数； y= f(指向树根的右孩子指针);//右子树中叶节点数； if(root->left==NULL&&root->right==NULL)return 1;
else return x+y; /*或者
if( x==0&&y==0)return 1; else return x+y;*/ }
int f ( btlink root ){//f()计算树中叶子节点的个数 if(root==NULL)return 0;
x=f(root->left); //左子树中叶节点数； y= f(root->right);//右子树中叶节点数； if(x==0&&y==0)return 1; else return x+y; }
T(n)=1+T(n1)+T(n2) n1+n2=n
=1+1+T(n11)+T(n12)+1+T(n21)+T(n22) n1=n11+n12 n2=n21+n22
25、二叉树以二叉表为存储结构，结点结构的定义如下，请写出一个求二叉树的高度算法。 解答：
int h(指向树根的指针){//f()计算树高度 if(指向树根的指针==NULL)return 0;
x=h(指向树根的左孩子指针); //左子树高度； y= h(指向树根的右孩子指针);//右子树高度； if(x>y)return x+1; else return y+1;
//return (x>y?x:y) +1; }
26、阅读下列程序，它是在已知的数组a中查找数值为x的元素，如果存在则输出“found”，否则输出“not found”。试问它是什么方法实现的？并请完善程序。
用__________查找法。 #define N 10
void bs(int a[],int x){ int l,r,m; l=0;r=N-1;
m=___(l+r)/2______;
while((_____l<=r_______) && (x!=a[m]) ){ if(x>a[m]) l=_____m+1______; else r=m-1; m=(l+r)/2; }
if(___l<=r____)
printf(\ else
printf(\}
main(){
int a[N]={10,20,30,40,50,60,70,80,90,100}; int x;
printf(\ scanf(\ bs(____a, x_______); }
05专升本数据结构考题
一、单选题：（每题2分，共24分）
1、双向链表的一个结点有( B )个指针。 A、1 B、2 C、0 D、3
2、在n个结点的顺序表中，算法的时间复杂度都是O(1)的操作是( A )。 A、访问第i个结点(1≤i≤n)和求第i个结点的直接前趋(2≤i≤n) B、在第i个结点后插入一个新结点(1≤i≤n) C、删除第i个结点(1≤i≤n) D、将n个结点从小到大排序
3、在队列中存取数据的原则是( A )。 A、先进先出 B、后进后出? C、先进后出 D、不进不出
4、在栈中，出栈操作的时间复杂度为( A )。 A、O(1) B、O(logn) C、O(n) D、O(n*n)
5、设长度为n的链队列用单循环链表表示，若只设头指针，则人队操作的时间复杂度为( C )。 A、O(1) B、0(logn) C、0(n) D、O(n*n)
6、如果二叉树的叶结点数为n0，则具有双分支的结点数n2等于( D )。 A、nO+l B、n0 C、2*n0 D、n0-1
7、一棵二叉树满足下列条件：对任一结点，若存在左、右子树，则其值都小于它的左子树上所有结点的值，而大于右子树上所有结点的值。现采用( B )遍历方式就可以得到这棵二叉树所有结点的递增序列。 A、先根 B、中根
C、后根 D、层次
8、用邻接表表示图进行深度优先遍历时，其非递归算法通常采用 ( A )来实现算法。
A、栈 B、队列 C、树 D、图
9、广度优先遍历类似于二叉树的( D )。 A、先序遍历 B、中序遍历 C、后序遍历 D、层次遍历
10、在一个有向图中，所有顶点的人度之和等于所有顶点的出度 之和的( B )。 A、1／2倍 B、1倍 C、2倍 D、4倍
11、任何一个带权无向连通图的最小生成树( B )。 A、只有一棵 B、一棵或多棵 C、一定有多棵 D、可能不存在
12、设非空单链表的数据域为data，指针域为next，指针P指向单链表的第i个结点，s指向生成的新结点，现将s结点插入到单链表中，使其成为第i结点，下列算法段能正确完成上述要求 的是( C )。 A、s->next=p->；p->next=s
B、p->next=s；s->next=p->next；
C、S->next=p->next；p->next=s；交换p->data和s->data D、p=s；s->next=p
二、填空题（每空2分，共20分）
1、数据的逻辑结构反映_____成分数据逻辑关系______。
2、对于队列，只能在___队尾_____插入元素，在____队头_____删除元素。 3、算法是一运算序列，它应有：有限性、____确定性____、可行性、可以无任何输入，但必须___有输出____。
4、由一棵二叉树的前序序列和____中序序列____可唯一确定这棵二叉树的结构。
5、如果图的存储结构用____邻接表/邻接矩阵___表示，从某指定顶点作为初始点进行广度优先搜索，得到的广度优先搜索序列唯一。
6、用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度____递增___的次序来得到最短路径的。
7、线性表(a1，a2，a3，??an)(n>=1)中，每个元素占c个存储单元，m为a1首地址，则按顺序存储方式存储线性表，ai存储地址是_____m+(i-1)*c___。 8、n个结点的无向图，最多有___n*(n-1)/2__条边。 三、应用题 (本大题共4小题，每小题8分，共32分)
1、用Prim算法求下图连通的带权图的最小代价生成树，在算法执行的某一刻，已选取的顶点集合U=[1，2，3]，边的集合 TE=[(1，2)，(2，3)]，要选取下一条权值最小的边，应当从哪些边中选择?
2、若用插入排序方法对线性表(25，84，21，47，]5，27，68，35，20)进行排序时，请给出前四趟排序结点序列的变化情况。 答：25
25 84 21 25 84 21 25 47 84 3、已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG和DECBHGFA，请画出该二叉树。
A / \\
BDCE FHG 中 DECB HGF 后
4、设将整数a，b，c，d依次进栈，请回答：若入、出栈次序为 Push(a)，Pop()，Push(b)，Push(c)，Pop()，Push(d)，Pop()， 则出栈的字符序列是什么? 答：acd
四、算法设计 (本大题共3小题，每小题8分，共24分)
1、二叉树以二叉链表为存储结构，类型声明如下，请写出一个求二叉树中结点个数的算法。
typedef struct node{ datatype data；
struct node *Lchild； struct node *Rchild； }BinaTree；
答：int f(BinaTree *t){
if(t = = NULL) return; else
return f(t->left)+ f(t->right)+1;
}
2、设线性表用顺序结构实现，声明如下： typedef struct sqlist{ char data[maxsize]； int n；
}Sqlist;
请写一个算法，判断其是否回文?(顺读与倒读 一样如：“ababbaba\为回文) 答：
解法1：形参和实参直接传递结构变量 #include
#define MAXLENGTH 100
typedef struct sqlist{
char data[MAXLENGTH]; int n; }Sqlist;
void f(Sqlist a){ int i;
if(a.n<=0)return;
for(i=0;i<(a.n)/2;i++){
if(a.data[i]!=a.data[a.n-i]){
printf(\return;
}
printf(\ } }
void main(){ Sqlist s;
printf(\输入n: \ scanf(\
printf(\输入字符串: \ scanf(\ f(s); }
解法2：形参是指针变量，实参是结构变量地址值 void f(Sqlist *a){ int i;
if(a->n<=0)return; for(i=0;i<(a->n)/2;i++)
if(a->data[i]!=a->data[a->n-i-1]){ printf(\ return; }
printf(\}
void main(){
Sqlist s;
printf(\ scanf(\ printf(\ scanf(\ f(&s); }
解法3：类似解法2，为指针变量定义了类型List #include
#define MAXLENGTH 100
typedef struct sqlist *List;
typedef struct sqlist{
char data[MAXLENGTH]; int n; }Sqlist;
void f(List a){ int i;
if(a->n<=0)return; for(i=0;i<(a->n)/2;i++)
if(a->data[i]!=a->data[a->n-i-1]){ printf(\ return; }
printf(\}
void main(){ Sqlist s;
printf(\ scanf(\ printf(\ scanf(\ f(&s); }
3、阅读下列程序，判断它是用什么方法实现排序(升序)的?并完善下列程序。 #include
void bubble(int[],int);
main(){
int array[]={55，2，6，4，32，12，9，73，26，37}; int size=sizeof(array)/sizeof(int)； bubble(_array,10___)； }
void bubble(int a[]，int size){ int i，temp；
int end_____=0__________； int pass=1；
//======================= while(!end&&pass for(i=0，i end=___0__________； } __pass++__________________; } //======================= for(i=0；i 第二部分 数据结构（共100分） 一、单项选择题（本大题共12小题，每小题2分，共24 分） 在每小题列出的四个备选项中只有一个符合题目要求，请将正确答案代码填写在答题纸相应的位置上。写在试卷上不得分。 1．在待排序记录已基本有序的前提下,下述排序方法中效率最高的是： A)直接插入排序 B)简单选择排序 C)快速排序 D)归并排序 2．以下哪一个术语与数据的存储结构无关？ A)栈 B)闭散列表 C)线索二叉树 D)双向链表 3．有6个元素6,5,4,3,2,1的顺序进栈，问下列哪一个不是合法的出栈序列： A)5,4,3,6,1,2 B)4,5,3,1,2,6 C)3,4,6,5,2,1 D)2,3,4,1,5,6 4．下述哪一条是顺序存储方式的优点？ A)存储密度大 B)插入运算方便 C)删除运算方便 D)可方便地用于各种逻辑结构的存储表示 5．对于只在表的首、尾进行插入操作的线性表，宜采用的存储结构为: A) 顺序表 B) 用头指针表示的单循环链表 C) 用尾指针表示的单循环链表 D) 单链表 6．对包含n个元素的散列表进行查找，平均查找长度 A)为O(log2n) B)为O(n) C)为O(nlog2n) D)不直接依赖于n 7．下列哪一种图的邻接矩阵是对称矩阵？ A)有向图 B)无向图 C)AOV网 D)AOE网 8. 设表 (a1, a2, a3, ......, a32) 中的元素已经按递增顺序排好序，用二分法检索与一个给定的值k相等的元素，若a1 A）2 B）3 C）4 D）5 10．对二叉树从1开始编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号， 则可采用的编号方法是： A、先序遍历 B、中序遍历 C、后序遍历 D、从根开始进行层次遍历 11. 在长度为n的顺序表的第i ( 1≤ i ≤n+1 )个位置上插入一个元素，元素的 移动次数为： A) n-i+1 B) n-i C) i D) i-1 12. 对于一个无向图，下列说法正确的是 A)每个顶点的入度大于出度； B)每个顶点的度等于其入度与出度之和； C)无向图的邻接矩阵一定是对称矩阵； D)有向图中所有顶点的入度之和大于所有顶点的出度之和； 二、填空题（本大题共10小题，每空2分，共22 分） 请在答题纸相应的位置上填写正确答案。写在试卷上不得分。 13. 设一哈希表表长M为100 ，用除留余数法构造哈希函数，即H（K）=K % P （P<=M）, 为使函数具有较好性能，P应选 97 14. N个结点的二叉树采用二叉链表存放，共有空指针域个数为 N+1 15. 若一个算法中的语句频度之和为T(n) = 3720n+4nlogn，则算法的时间复杂 度为_______O(nlogn)_________ 。 16. 已知有向图的邻接矩阵，要计算i号结点的入度，计算方法是： 将 第i列 累加。 17. 深度为6（根深度为1）的二叉树至多有 63 个结点。 18. 一棵具有n个叶子结点的哈夫曼树中，结点总数为 2n-1 。 19. 设单链表结点的定义如下： struct node{ int data, struct node *next; }; 要在一个单链表中p所指结点之后插入一个子链表，子链表第一个结点的地址为s，子链表最后一个结点的地址为t, 则应执行操作： t->next=p->next;________ 和 _________ p->next=s； 。 20. 设单链表结点的定义如19题，现有一个含头结点的单链表，头指针为head, 则判断该单链表是否为空表的条件为 head->next==NULL 。 21. n个顶点的连通无向图至少有 n-1 条边。 22. 在顺序存储结构的线性表中插入一个元素，平均需要移动 n/2 个元素. 三、应用题：（本大题共4小题，每小题8分，共32 分） 请在答题纸相应的位置上填写正确答案。写在试卷上不得分。 23． 已知有向图如图1所示： （1）写出顶点B的度（2分）； （2）写出从结点D开始的两个广度优先搜索序列（2分）； （3）画出该图的邻接表（4分）。 解答: （1）顶点B的度:_______3________ (2分) （2）_________DBCA______和_____DCBA______ (2分) （3）(4分) A B C 图 1 D 或 24. 已知二叉树的中序序列为DBGEAFC，后序序列为DGEBFCA，画出对应的二叉树。 解答: A / \\ B C / \\ / D E F / G 25. 图2表示一个地区的通讯网，边表示城市间的通讯线路，边上的权值表示架设线路花费的代价，请画出该图的最小代价支撑树，并计算最小代价支撑树的权。 图2 解答: （每条边1分，画方框的两条边任选一条） 最小代价支撑树的权=56 （3分） 26. 设一个闭散列表具有10个桶，散列函数H（x）=x%7，若元素输入顺序为： {50，42，85，22，76，19，34，68}，解决冲突用线性重新散列技术，要求画出构造好的散列表。 解答:（8分，第二行每个数字1分） 0 42 1 50 2 85 3 22 4 5 19 6 76 7 34 8 68 9 四、算法设计（本大题共2小题，第27小题10分，第28小题12分，共22 分） 请在答题纸相应的位置上填写正确答案。写在试卷上不得分。 27.二叉搜索树T用二叉链表存储结构表示，其中各元素的值均不相同。编写算 法，按递减顺序打印T中各元素的值。结点结构定义如下： typedef int TreeItem; typedef struct btnode *btlink; typedef struct btnode{ TreeItem data; btlink left, right; }BTNODE; 解答: void f(btlink t) { // 或void f(BTNODE *t) if(t){ f(t->right); printf(\ f(t->left); } } 28. 阅读下面程序，其功能是调整线性表中的元素，将所有奇数放在表的左边，将所有偶数放在表的右边。请填空完成该程序。（每空1分，共12 分） #define MAXSIZE 100 typedef int ElemType; typedef struct{ ElemType elem[MAXSIZE]; int last; /*末元素下标*/ }SeqList; void AdjustSqlist(SeqList *L){ ElemType temp; int i=0, j= ⑴ ; while(i while(L->elem[ ⑵ ]%2 != 0 && ⑶ ) i++; while(L->elem[ ⑷ ]%2 = = 0 && ⑸ ) j--; if( ⑹ )break; temp = L->elem[i]; } } L->elem[i]= ⑺ ; L->elem[j]= ⑻ ; void main(){ SeqList ⑼ ; int r, i; } 解答:（每空1分，共12分，大小写不能错） ⑴、_______ L->last _____________ ⑶、_______ i ⑵、_______ i ______________________ ⑷、_______ j ______________________ ⑹、_______ i>=j ___________________ ⑻、______ temp __________________ ⑽、_______SeqList *_____________ ⑿、_______sq->elem[i]____________ sq=( ⑽ )malloc(sizeof(SeqList)); printf(\请输入线性表的长度:\scanf(\ sq->last = ⑾ ; printf(\请输入线性表的各元素值:\\n\ for(i=0; i<=sq->last; i++) scanf(\ ⑿ ); AdjustSqlist(sq); 08专升本数据结构考题解答 一、 单项选择题（共12小题，每小题2 分，共24分） 1．用非递归方法实现递归算法时通常要使用 A．循环队列 B．栈 C．二叉树 D．双向队列 2．对于一个具有n个顶点和e条弧的赋权有向图，如果用赋权邻接矩阵表示这个图，请问求单源最短路径的Dijkstra算法的时间复杂度为 A．O(n) B．O(n+e) 3．设语句x++的执行时间时单位时间，以下语句的时间复杂度是 for(i=1; i<=n; i++) for(j=1; j<=n; j++) x++; C．O(n*n*n) D．O(n*n) C．O(n*n) D．O(2e) A．O(1) B．O(n) 4．一高度为h的非空二叉树（假设只含根节点的树的高度为1）最多有几个节点 A．2h 5．赋权有向图G用用赋权邻接矩阵A存储，则节点i的入度等于 A．第i行非∞的元素之和 B．第i列非∞的元素之和 D．第i列非∞且非0的元素个数 B．2h-1 C．2h-1 D．2h C．第i行非∞且非0的元素个数 6．设双链表的节点类型定义如下， typedef typedef struct node *link; struct node{ ListItem element; link left; link right; }*p,*q,*r; 删除双链表中节点p(由p指向的节点)的操作是 正确的做法如下图： A． q=p->left; r=p->right; q->right=r; r->left=q; 正确的 B． q=p->right; r=p->left; q->right=r; r->left=q; 把A的p和q反过来，结果错了。 C． q=p->left; r=p->right; q->left=r; r->right=q; 错误，与B一样，只是把p和q反过来。 D．q=p->left; r=p->right; q->right=r->left; 什么也没有变化。 7．会引起循环队列队头位置发生变化的操作是 A．出队列 8．如图1所示，若从顶点1出发进行广度优先搜索，则得到的访问序列是 A． 1,8,3,4,5,6,7,2 B． 1,2,3,7,5,6,4,8 C． 1,2,5,4,3,6,7,8 D．1,2,3,4,5,6,7,8 9．下列排序算法中，不受数据初始状态影响，时间复杂度为O(n*logn)的是 A．堆排序 10．用指针实现二叉树，在n个节点的二叉树中含有多少个空指针？ A．n 11．用一棵二叉搜索树进行( )得到的是有序序列。 A．前序遍历 12．合并排序算法的时间复杂度是 A．O(n2) 二、 填空题（共7小题，每空2 分，共16分） 13．在一个长度为n的顺序表的第i（1<=i<=n）个元素之前插入一个元素，需要 B．O(nlogn) C．O(logn) D．O(n) B．中序遍历 C．后序遍历 D．层次遍历 B．n-1 C．n+1 D．2n B．冒泡排序 C．直接选择排序 D．快速排序 B．入队列 C．取队首元素 D．取队尾元素 后移___n-i+1____个元素。 14．设某哈夫曼树有n个叶子节点，则该哈夫曼树的总结点数为__2n-1__。 15．设有一个序列8,53,37,28，当使用直接插入排序从小到大排序时，比较次数是____5____。 16．设SQ为循环队列，存储在数组queue[0…m-1]中，则SQ入队操作对其队尾指针rear的修改是___ (rear+1)%m___。 17．设待排序的序列中存在多个记录具有相同的键值，经过排序，这些记录的相对次序仍然保持不变，则称这种排序是__稳定的____，否则称为___不稳定的___。 18．在一个具有n个顶点的无向图中，要连通所有的顶点至少需要__n-1____条边。 19．在有向图中，以顶点v为起点的弧的数目称为v的___出度__。 三、 应用题（共4小题，每小题10 分，共40分） 20．已知关键字序列(12,77,21,65,38,7,40,53)，采用直接插入排序按递增排序，给出每一趟的结果。 12,77,21,65,38,7,40,53 12,21,77,65,38,7,40,53 12, 21,65, 77,38,7,40,53 12, 21, 38,65, 77, 7,40,53 7,12, 21, 38,65, 77, 40,53 7,12, 21, 38,40,65, 77, 53 7,12, 21, 38,40,53,65, 77 21．已知散列表长度为10（散列空间0..9），使用线性重新散列技术解决冲突， 现有一组单词(SUN, MON, TUE , WED , THU, FRI, SAT)，其对应的散列函数值分别为(3,2,6,3,2,5,6)，请画出这组单词插入后的散列表。 0 1 2 MON 3 SUN 4 WED 5 THU 6 TUE 7 FRI 8 SAT 9 22．假设一个二叉树的先序为EBADCFHGIKJ，中序序列是ABCDEFGHIJK， （1） 画出二叉树；（2）写出后序序列。 先序为EBADCFHGIKJ，中序序列是ABCDEFGHIJK，根是E E / \\ ABCD FGHIJK 中 BADC FHGIKJ 先序 根B 根F / \\ / \\ A CD GHIJK 中 A DC HGIKJ 先序 根D 根H / / \\ C G IJK 中 IKJ 先 根I \\ JK中 KJ先 根K / J 最后结果： E / \\ B F / \\ \\ A D H / / \\ C G I \\ K / J 后序是：A C D B G J K I H F E 23．根据PRIM算法画出图2的最小生成树，要求画出从顶点1开始生成的过程。 解答： 四、 算法设计题（共2小题，每小题10 分，共20分） 24．下列程序将集合A和集合B归并成一个集合C，归并前集合A和集合B中的元素按非递减排列，归并后集合C的元素仍按非递减顺序排列，而且C不需 要新建节点空间。请完善程序。 typedef struct node{ ElemType data; struct node * next; }*LinkList 说明：*LinkList是指针类型，基类型是LNode。 void MergeSet(LinkList La, LinkList Lb){ LinkList pa , pb, pc , p; pa=La; pb=Lb; pc=NULL; while(_____pa!=NULL&& pb!=NULL __________){ if(pa->data<=pb->data){ if(pc!=NULL) { ______p->next=pa;________________ p=p->next; } else{ pc=pa; p=pc; }//if _____pa=pa->next_______________; } else{ if(pc!=NULL) { ____p->next=pb;_______________ p=p->next; } else{ pc=pb; p=pc; }//if ____pb=pb->next_____________; }//if }//while p->next=(pa!=NULL)?pa:pb; /*处理一个链表为空的情况*/ } 25．二叉排序（搜索）树t以二叉表为存储结构，请编写算法实现在该树上查找值为x的节点。 typedef int TreeItem; typedef struct btnode *btlink; typedef struct btnode{ TreeItem data; Btlink lchild, rchild; /*左右孩子指针*/ }BiTNode 算法函数原型BiTNode Locate(BiTNode *t, TreeItem x) 解答： BiTNode Locate(BiTNode *t, TreeItem x){ if(t = =NULL)return NULL: if( x = = t-> data ) return *t; /* 注意*，因为返回类型是BiTNode*/ else if( x < t-> data ) return Locate(t->lchild, x); /*左子树*/ else return Locate(t->rchild, x); /*右子树*/ } 09年专升本数据结构考题解答(共100分) 一、 单项选择题（12小题，每小题2分，共24分） 1、要表示高校校、系、班级的有关数据及其关系，选择______比较合适。 A. 线性结构 B. 树结构 C. 图结构 D.集合结构 2、下列函数中复杂度最小的是 A. T(n)=nlog2n+5000n B. T(n)=n2-8000n C. T(n)=nlog22n-6000n D. T(n)=2nlog22n-7000n nlog22n= nlog22+log2n=n1+log2n=n*n log2n 3、已知一个栈s以及一个输入序列(A，B，C，D，E)，每个元素按照A，B，C，D，E顺序进栈一次，进栈后可立即出栈，也可在栈中停留一段时间后再出栈，则不能得到（）序列。 A．A、B、C、D、E B. B、A、E、D、C C．C、B、A、D、E D. D、C、A、B、E 4、平均排序效率最好的排序方法是（）。 A．直接插入排序 B．快速排序 C．简单选择排序 D．冒泡排序 5、某链表中最常用的操作是在已知的一个结点之前插入一个新结点和删除其之前一个结点，则采用（）存储方式最节省运算时间。 A．双向链表 B．带头指针的单向链表 C．带尾指针的单向链表 D．单向循环链表 6、在逻辑结构不变的情况下，不是导致一个图的遍历序列不唯一的因素是（）。 A．出发点不同 B．存储(物理)结构不同 C．遍历方法不同 D．画法不同 7、散列函数有一个共同的要求，即函数值应当尽量以（）取其值域的每个值。 A．最大概率 B．最小概率 C．正态分布概率 D．均等概率 8、下面（）方法可以判断出一个图中是否存在环(回路)。 A．排序 B．深度和广度遍历 C．求最短路径 D．求关键路径 9．最佳二叉搜索(排序)树是（）。 A．关键码个数最小的二叉搜索树 B．退化为线性的二叉搜索树 ， C．搜索中平均比较次数最小的二叉搜索树 D．任何结点的度数为0或2的二叉搜索树 10．（）是数据的基本单位，即数据集合(对象)中的个体。 A．数据结构 B．数据项 C．数据元素 D．数据对象 11． (线性)表是一个（）。 A．有限序列，可以为空 B．有限序列，不能为空 C．无限序列，可以为空 D．无限序列，不能为空 12．树是结点的集合，它（）根结点。 A．有0个或1个 B．有0个或多个 C．有且只有1个 D．有1个或1个以上 二、填空题(本大题共7小题，每空2分，共16分) 请将答案写在答题纸相应的位置上。 13． 在有n个顶点的有向图中，每个顶点的度(=入度+出度)最大可达（2n-2）。 14． 以下程序段的时间复杂度是（）。 i=0； j=0; while ( i+j<=n) { if(i>j)j++; else i++； } 每次只做i++或j++，不会同时 i++而且j++， n的值不变，因此循环n次，复杂度O(n) 15． 右图所示的二叉树后序遍历的结果是（EDCBIHJGFA）。 16． 在一个双向链表中p所指结点之前插入一个由指针s所指的新结点，写出可执行的操作序列：（）。(前指和后指的指针域分别为prior和next) 1. s->prior=p->prior； 2. s->next=p； 1和2顺序可换 3. p->prior->next=s； 4. p->prior=s； 注意p->prior要最后改变，因为之前要用 17. (线性)表有两种存储结构：顺序存储结构和链式存储结构，请就这两种存储结构完成下列填充：（顺序存储结构）存储密度较大，可以随机存取：（链式存储结构）不可以随机存取，插入和删除操作比较方便。 18．递归的程序执行时使用（堆栈）来保存各层递归调用时的现场信息，以保证可以正确返回。 19．设数组a[M](M为最大空间个数)作为循环队列Q的存储空间，front为队头指针(指向第一个存放数据的位置)，rear为队尾指针(指向最后一个存放数据位置的下一个)，则判定Q队列的队满条件是（）。 队满条件与方案无关，总是(rear+1)%n==front 三、应用题(本大题共4小题，每小题10分，共40分) 请将答案写在答题纸相应的位置上。 20．设字符集D={A，B，C，D，E}，各字符使用频率W={10，2，5，6，4}，画出对字符进行哈夫曼编码时所对应的哈夫曼树，并给出各字符的编码。 21．用普里姆(Prim)算法从右图中的顶点1开始逐步构造最小支撑(代价生成)树，要求画出构造的每一步。 22．给定待排关键字集合为{23，14，48，25，5，19}，按关键字非递减(从小到大)排序，写出采用冒泡排序的每一趟(最外层循环的每一次)排序结果。 23．(1)图示表示右边有向图的邻接表。(4分) (2)写出从顶点1开始分别进行深度优先和广度优先遍历的顶点序列各一种。(6分) 四、算法设计题(本大题共2小题，每小题10分，共20分) 请将答案写在答题纸相应的位置上。 24．假定用一个有头结点循环链表来存储一个有序的线性表，线性表从头到尾 为非递减(从小到大)有序(如下图)。用指针current从head开始搜索数据域等于key的元素在线性表中位置，如果搜索成功则current指向搜索到的结点，函数返回该指针：如果搜索不成功，函数返回空指针NULL。请在函数 SortedlistLocate(head，key) 内填空，完成下列算法以实现这种搜索，并使得搜索不成功的平均比较次数小于链表长度。（发现current指向结点的数据域比key大，则停止搜索，后面肯定没有key，搜索失败。这样就没有必要走到链表的尾部，不成功的平均比较次数=(0+1+2+..+n)/(n+1)=n/2） 注意：有头结点，是单循环链表。空表如下 typedef struct node{ elemtype data；/*数据域*/ struct node next；/*指针域*/ }lnode，*linklist； 注意typedef，lnode和linklist是类型名 linklist SortedlistLocate ( linklist head， elemtype key){ linklist current； if(_head==NULL_)return ERROR； /*错误提示*/ current ___=head->next____; /*循链搜索其值等于key的结点*/ while(_current!=head_&&_current->data current=current-->next； /*排除空表*/ if ( _ current !=head && current->data==key _) return current； /*找到，返回结点地址*/ else return NULL； /*末找到，返回空指针*/ } 25．r[]为一维数组，其中r[0]到r[n-1]为待排序的n个元素，排序好的元素仍放在r[0]到r[n-1]中。请写出对该数组进行非递减排序的直接插入排序算法， 取名为InsertSort(elemtype r[]，int n)。