专升本十套-数据结构(试题及答案).doc

数据结构试卷（一）
一、单选题（每题 2　分,共20分）
1. 栈与队列得共同特点就是( 　 )。
A、只允许在端点处插入与删除元素
Ｂ、都就是先进后出
C、都就是先进先出
D、没有共同点
2. 用链接方式存储得队列,在进行插入运算时（ 　）、
A、 仅修改头指针　 　 　 B、 头、尾指针都要修改
　　　　　C、 仅修改尾指针 　　　　 Ｄ、头、尾指针可能都要修改
3. 以下数据结构中哪一个就是非线性结构？(　 )
　 Ａ、　队列　 　 　 Ｂ、 栈 　　　 C、　线性表　　　 　 Ｄ、　二叉树
4. 设有一个二维数组A[m］［n］，假设Ａ［0］[０］存放位置在644（10）,A［２］［2］存放位置在６76（１0）,每个元素占一个空间，问A[3］[3](10)存放在什么位置？脚注(１0）表示用10进制表示。
　 　 　 A.6８8 　 　 B．６７8 　　 C.6９2　 　 　 D．69６
5. 树最适合用来表示（ 　 　)。
　 Ａ、有序数据元素 　 　 　 　 　　 　 B、无序数据元素
　 C、元素之间具有分支层次关系得数据 　 D、元素之间无联系得数据
6. 二叉树得第k层得结点数最多为( )、
　 　　Ａ。２ｋ—１　 　 B、2K+1 　　　C、2K-1 　 D、 2k-１
7. 若有１8个元素得有序表存放在一维数组A［19]中，第一个元素放A［１]中,现进行二分查找，则查找Ａ［3］得比较序列得下标依次为( 　 　)
　 A、　1,2,3 ﻩ ﻩＢ、 9，5，2，３
　 C、 9，５,3 ﻩﻩﻩ D、 9,4，2，3
8. 对ｎ个记录得文件进行快速排序，所需要得辅助存储空间大致为
　　　 A、 Ｏ(1） 　　Ｂ、　O（ｎ）　 C、 O（1og2n) 　 　 　D、 O(n２)
9. 对于线性表(7,34,5５，25,64，４6，20,10）进行散列存储时，若选用H（K）=K %9作为散列函数,则散列地址为1得元素有（ 　）个，
　A。1 　 　 B．2 　 　　　 　　C．3 　 　 　 D．4
10. 设有6个结点得无向图,该图至少应有（ 　 　　)条边才能确保就是一个连通图。
　 A、5　 　B、6 　 C、7 　 　Ｄ、8
二、填空题（每空1分,共26分）
1. 通常从四个方面评价算法得质量：__＿＿＿_＿__、_________、______＿__与____＿_＿__.
2. 一个算法得时间复杂度为（n３＋ｎ2ｌog２n+14n）／n２,其数量级表示为________.
3. 假定一棵树得广义表表示为A(C，Ｄ（E,F，G），H(I，J）），则树中所含得结点数为__＿_______个，树得深度为________＿__，树得度为__＿______。
4. 后缀算式9 2 3 +— 1０　2 ／ —得值为_______＿＿_.中缀算式（３+4X)－2Y/3对应得后缀算式为__＿___＿＿____＿_＿_＿____＿___＿__＿＿＿。
5. 若用链表存储一棵二叉树时,每个结点除数据域外，还有指向左孩子与右孩子得两个指针。在这种存储结构中,n个结点得二叉树共有＿____＿__个指针域，其中有______＿_个指针域就是存放了地址，有______＿___＿_____个指针就是空指针。
6. 对于一个具有n个顶点与e条边得有向图与无向图,在其对应得邻接表中，所含边结点分别有＿____＿_个与_＿__＿＿_＿个。
7. AOV网就是一种＿______＿_____＿_＿___得图。
8. 在一个具有n个顶点得无向完全图中，包含有__＿_＿___条边，在一个具有n个顶点得有向完全图中，包含有___＿___＿条边。
9. 假定一个线性表为（12，23，７４,５５，６3，４0)，若按Keｙ ％ 4条件进行划分，使得同一余数得元素成为一个子表，则得到得四个子表分别为＿__＿_＿＿____＿______＿__＿_＿____、＿____＿＿_＿＿_＿______＿、＿__＿__＿______＿____＿_＿＿_与＿＿___＿＿＿___＿_＿＿___＿＿＿__＿__。
10. 向一棵B_树插入元素得过程中,若最终引起树根结点得分裂，则新树比原树得高度_______＿_＿_。
11. 在堆排序得过程中,对任一分支结点进行筛运算得时间复杂度为___＿__＿_,整个堆排序过程得时间复杂度为__＿＿__＿_。
12. 在快速排序、堆排序、归并排序中，_＿_______排序就是稳定得.
三、计算题（每题　６ 分,共２4分)
1. 在如下数组A中链接存储了一个线性表，表头指针为Ａ ［0]、ｎext，试写出该线性表.
　 　 　 　　 　 Ａ　 　　0 　 　　1　 2 　 3 4　 　　 5　　 　6 7　
data

6

nexｔ
3
5
7
2
０
4

1
2. 请画出下图得邻接矩阵与邻接表。

3. 已知一个图得顶点集V与边集E分别为：V={1，2，3,４，5，6,７}；
　　 E=｛(1，２)3，（1，3）5，(1，4）８，（２，５）１0,（２,3）6，（３，4）1５,
（３，5)1２,（3,6)９，（４,６）4，（4，７）20，（5,6）18,（6,7）25｝；
　 用克鲁斯卡尔算法得到最小生成树,试写出在最小生成树中依次得到得各条边。
4. 画出向小根堆中加入数据4， 2,　５, 8， 3时，每加入一个数据后堆得变化。
四、阅读算法（每题7分,共1４分)
1. ＬｉnｋLｉsｔ mｙｎｏｔe（LinkLiｓt L)
　　　 ｛/／Ｌ就是不带头结点得单链表得头指针
　 　if(L&＆Ｌ—〉next）{
　 　 　 　 q＝L;L=Ｌ—〉next;p=L；
　 　　　 S1: 　 whｉle（p->ｎeｘt） ｐ=ｐ—>next;
　　 S２： 　 p－〉ｎeｘt=q；q—〉ｎexｔ＝ＮULＬ;
　　 　 }
　 　ｒeturn 　L；
　 }
　　 请回答下列问题：
(1)说明语句Ｓ1得功能;
　（2）说明语句组S2得功能;
（３）设链表表示得线性表为(ａ1，a2， …,aｎ)，写出算法执行后得返回值所表示得线性表.
2. voｉｄ AＢＣ（BTNｏde　＊　ＢＴ)
｛
　 　 if ＢＴ {
　 　 AＢC　（BＴ－〉leｆt);
　 　 ABC　（BT—>rｉght);
　 　 ｃout＜＜BＴ—>dａta〈〈’ ’；
　 　｝
　 ｝
　 　　该算法得功能就是:
五、算法填空（共8分）
二叉搜索树得查找—-递归算法:
ｂoｏl Finｄ（ＢＴrｅeＮode＊ BＳT，ElemＴyｐe& itｅm)
｛
iｆ (BSＴ=＝NＵLL）
　 rｅtｕrｎ falsｅ; ／／查找失败
　eｌｓe ｛
　 　　if　(itｅｍ＝＝BST—>daｔa)｛
　　　 　 iteｍ=BSＴ-〉ｄａta;//查找成功
　 　 　　　　 ｒeturn 　..____＿_＿___＿；｝
　　 　 elｓe ｉf(itｅm〈BSＴ—>ｄａta）
　 　 　 　 rｅｔｕrn　 Finｄ（__________＿___，iｔｅm）；
eｌse reｔurｎ Ｆinｄ（____＿__＿＿___＿＿_,iｔem）；
　 　 ｝//iｆ
}
六、编写算法（共8分）
统计出单链表HＬ中结点得值等于给定值X得结点数。
　 ｉnｔ CｏｕntX(LNｏde＊ HＬ,ＥlemTｙpe x)
数据结构试卷(二)
一、选择题（24分）
１.下面关于线性表得叙述错误得就是( )。
ﻩ（Ａ)　线性表采用顺序存储必须占用一片连续得存储空间ﻩ
(B） 线性表采用链式存储不必占用一片连续得存储空间
（Ｃ) 线性表采用链式存储便于插入与删除操作得实现
（Ｄ） 线性表采用顺序存储便于插入与删除操作得实现
2。设哈夫曼树中得叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（ ）个空指针域。
（Ａ）　2m－１ (B） ２m (C） ２m+１ﻩ（D) ４m
3.设顺序循环队列Q［0:Ｍ—1]得头指针与尾指针分别为F与R,头指针Ｆ总就是指向队头元素得前一位置,尾指针R总就是指向队尾元素得当前位置，则该循环队列中得元素个数为（ ）。
（Ａ） R—Ｆ （B）　F－Rﻩ（C） (Ｒ－F+M)％Ｍﻩ（D) （F-R+Ｍ)%Ｍ
４.设某棵二叉树得中序遍历序列为AＢCD,前序遍历序列为CＡBD,则后序遍历该二叉树得到序列为(　 　）。
(Ａ） ＢADＣ (B) ＢCDＡ (Ｃ） CＤABﻩ(D） CBDA
５。设某完全无向图中有ｎ个顶点，则该完全无向图中有（ )条边。
ﻩ（A) n（n—１）／2ﻩ（B） n（n-１）ﻩ（C) n2 ﻩ(D) n2—1
6．设某棵二叉树中有2０00个结点，则该二叉树得最小高度为（ ）.
（A) 9 （Ｂ） 10ﻩ(C)　１１ (Ｄ) 12
7.设某有向图中有ｎ个顶点，则该有向图对应得邻接表中有( )个表头结点.
ﻩ（A） n-１ﻩ（B） ｎﻩ(C) n+1ﻩ(Ｄ) ２n－1
8。设一组初始记录关键字序列(５,２,6，3，8),以第一个记录关键字5为基准进行一趟快速排序得结果为（ )。
ﻩ(Ａ） ２，3，5，8，6 ﻩ(B)　3，2，5,8，6
ﻩ(C）　3，２，５,6,8ﻩ (D） ２,3,6,5,8
二、填空题（24分）
1. 为了能有效地应用HAＳＨ查找技术,必须解决得两个问题就是_＿_＿_＿___＿＿___＿_＿___与______＿__＿__＿__＿_＿＿_______。
2. 下面程序段得功能实现数据x进栈，要求在下划线处填上正确得语句.
typeｄeｆ strucｔ ｛int s［1０0］； ｉnt top;｝ sqｓtack；
ｖｏid pｕsh(sqstａck ＆sｔａck，int x)
{
if （staｃk、toｐ==m－１） priｎtf(“ovｅrfｌow”）;
eｌｓe　｛__＿＿＿__＿________＿___；_＿___＿__＿__＿____＿；｝
}
3. 中序遍历二叉排序树所得到得序列就是___＿_______序列（填有序或无序)。
4. 快速排序得最坏时间复杂度为__________＿,平均时间复杂度为________＿_.
5. 设某棵二叉树中度数为０得结点数为N0，度数为1得结点数为N１，则该二叉树中度数为2得结点数为＿___＿____；若采用二叉链表作为该二叉树得存储结构,则该二叉树中共有__＿____个空指针域。
6. 设某无向图中顶点数与边数分别为n与e，所有顶点得度数之与为d，则e=_______.
7. 设一组初始记录关键字序列为（55，63，44,38，７5,80,31,５6），则利用筛选法建立得初始堆为__＿__＿＿________＿_＿＿________。
8。　已知一有向图得邻接表存储结构如下：从顶点1出发，DFS遍历得输出序列就是
　 　,BＦS遍历得输出序列就是　 　 　

三、应用题(3６分）
1． 设一组初始记录关键字序列为（4５,８0，48，４0，2２，78），则分别给出第4趟简单选择排序与第4趟直接插入排序后得结果。
2． 设指针变量p指向双向链表中结点A,指针变量q指向被插入结点B,要求给出在结点A得后面插入结点B得操作序列（设双向链表中结点得两个指针域分别为llink与ｒliｎk）。
3． 设一组有序得记录关键字序列为(１3，1８，24,35，47，50，62，８３,90)，查找方法用二分查找,要求计算出查找关键字62时得比较次数并计算出查找成功时得平均查找长度.
4． 设一棵树T中边得集合为｛（Ａ，B），(A,C),（A,Ｄ），(B，E)，(C，F)，(C，G）｝，要求用孩子兄弟表示法(二叉链表）表示出该树得存储结构并将该树转化成对应得二叉树。
5． 设有无向图Ｇ,要求给出用普里姆算法构造最小生成树所走过得边得集合.

6． 设有一组初始记录关键字为(45，８０，48,4０，22,７8),要求构造一棵二叉排序树并给出构造过程。
四、算法设计题(16分）
1． 设有一组初始记录关键字序列（K1,K2，…，Kｎ），要求设计一个算法能够在O（n)得时间复杂度内将线性表划分成两部分,其中左半部分得每个关键字均小于Kｉ,右半部分得每个关键字均大于等于Ｋi。
2． 设有两个集合A与集合B,要求设计生成集合Ｃ＝A∩B得算法，其中集合A、B与Ｃ用链式存储结构表示。
数据结构试卷(三）
一、选择题(每题1分,共２０分）
1。设某数据结构得二元组形式表示为A=（D，R），D＝｛0１,02，03，04，05，０6,0７，0８，09},Ｒ={r｝,r={<01，0２>，＜01，03>,〈01，０4>，〈02，05〉，<０2，０6>，〈0３,07>,〈０3，08>，〈0３，09>｝，则数据结构A就是（　 )。
ﻩ（A） 线性结构 （B) 树型结构ﻩ(C）　物理结构 （D） 图型结构
2．下面程序得时间复杂为（ ）
for(i=1,s＝０； i<=n； i＋+)　｛t=１；for(j＝１；j<=i；ｊ++） ｔ＝ｔ＊j；s=ｓ+t;｝
（Ａ） O（n)ﻩ（B)　Ｏ(n２） （C） O（n3） ﻩ（D) O(n４)
3.设指针变量ｐ指向单链表中结点A，若删除单链表中结点A，则需要修改指针得操作序列为( ）.
ﻩ（A） q＝p—〉neｘｔ;p->data=q—〉ｄaｔａ;ｐ—〉next＝ｑ->neｘt;ｆｒee（q）；
(B） q=p—〉nｅxt；ｑ-＞datａ=p-〉ｄａta；ｐ－>next＝q—＞ｎext；free（ｑ)；
ﻩ(C） ｑ＝p—>next；p－>next=ｑ-＞next；frｅｅ(q）;
(D） q＝ｐ—>next;p->data=ｑ—>ｄatａ;fｒｅe(ｑ);
４。设有n个待排序得记录关键字，则在堆排序中需要（ ）个辅助记录单元。
ﻩ(A)　１ﻩ(B) n （C) ｎloｇ2n （D) ｎ２
5。设一组初始关键字记录关键字为（２0，１5,14,18,21，３６，40,１0）,则以2０为基准记录得一趟快速排序结束后得结果为(　　）。
(Ａ） 10,１5,14,１8,20,3６，40，２１
(B)　１0，1５，１４,１8，20，40,36,21
(C）　10，15,１4，20,1８,40，36,2l
ﻩ（D） 1５,10，14，18,2０，36，40，21
６。设二叉排序树中有n个结点，则在二叉排序树得平均平均查找长度为( ).
(A） O(1） (B) O（ｌｏｇ2n) （C)ﻩ（D） O（n２)
７．设无向图Ｇ中有n个顶点e条边，则其对应得邻接表中得表头结点与表结点得个数分别为（ ）。
ﻩ(A）　n,e （B) ｅ，n （C) 2n,e （D)　n,2e
8、　设某强连通图中有n个顶点，则该强连通图中至少有（　 ）条边。
（A) n(ｎ-1）ﻩ（B) ｎ+１ （C) n （D） n(n＋1)
9。设有5００0个待排序得记录关键字，如果需要用最快得方法选出其中最小得１0个记录关键字,则用下列( )方法可以达到此目得。
ﻩ（A) 快速排序 (B) 堆排序ﻩ(C) 归并排序ﻩ（D） 插入排序
10、下列四种排序中( ）得空间复杂度最大.
（A） 插入排序ﻩ（Ｂ） 冒泡排序 （Ｃ）　堆排序 （Ｄ） 归并排序
二、填空殖(每空1分 共2０分）
1. 数据得物理结构主要包括_____＿_______与__＿＿_＿______＿_两种情况.
2. 设一棵完全二叉树中有50０个结点,则该二叉树得深度为＿___＿___＿_;若用二叉链表作为该完全二叉树得存储结构，则共有_＿___＿_____个空指针域。
3. 设输入序列为１、2、3,则经过栈得作用后可以得到_＿_＿_______种不同得输出序列。
4. 设有向图G用邻接矩阵A[n][n］作为存储结构，则该邻接矩阵中第i行上所有元素之与等于顶点i得_____＿__,第i列上所有元素之与等于顶点i得＿____＿__。
5. 设哈夫曼树中共有n个结点，则该哈夫曼树中有____＿_＿_个度数为1得结点。
6. 设有向图G中有ｎ个顶点ｅ条有向边,所有得顶点入度数之与为d,则e与d得关系为_______＿＿.
7. ＿______＿__遍历二叉排序树中得结点可以得到一个递增得关键字序列（填先序、中序或后序）。
8. 设查找表中有10０个元素,如果用二分法查找方法查找数据元素X,则最多需要比较＿_______次就可以断定数据元素X就是否在查找表中.
9. 不论就是顺序存储结构得栈还就是链式存储结构得栈，其入栈与出栈操作得时间复杂度均为＿________＿__。
10. 设有n个结点得完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号,则第i个结点得双亲结点编号为＿_＿____＿_＿__，右孩子结点得编号为＿＿______＿__。
11. 设一组初始记录关键字为(72，73，７1，２３，９4，１6,5），则以记录关键字7２为基准得一趟快速排序结果为___＿＿＿＿__＿_____＿＿＿_＿＿_＿＿___。
12. 设有向图Ｇ中有向边得集合E=｛〈1，2〉，＜２,3＞，＜1,4＞,〈4，2＞,＜４,3>｝，则该图得一种拓扑序列为______＿___＿_＿＿______.
13. 下列算法实现在顺序散列表中查找值为ｘ得关键字，请在下划线处填上正确得语句。
ｓｔrucｔ　record｛int key; ｉｎｔ othｅrs;｝；
ｉｎt　hashsqｓearch(strｕct recorｄ hashtable［ ］,inｔ ｋ)
｛
int ｉ,j； j＝i=k %　ｐ；
whilｅ （hasｈtaｂｌｅ［j］、kｅy！=k＆&haｓhtabｌe[ｊ]、ｆlａg!=０){ｊ=(____）　%ｍ; if　（i==j) retuｒｎ(—1）；｝
　　if　（__＿＿＿_＿_＿＿＿__＿＿＿_＿___＿_ ） rｅturn(j); eｌse rｅturn(－1）；
｝
14. 下列算法实现在二叉排序树上查找关键值k,请在下划线处填上正确得语句。
typeｄef　stｒｕct　ｎoｄe{int kｅｙ;　ｓｔrucｔ　node *lchｉld；　ｓtrｕｃｔ ｎode ＊rchild;}bｉtｒｅｅ;
bitｒｅe ＊ｂstsearcｈ(bｉtrｅe　*ｔ， int　 k)
{
ｉｆ　（t=＝０ ） retuｒn（0）；elｓe whｉlｅ (t！＝0）
if （ｔ—〉keｙ＝=k）_＿＿__＿＿_＿_＿＿_； elｓe if　(t—>kｅy〉k）　ｔ=ｔ－＞lcｈilｄ； ｅｌsｅ＿_＿＿____＿_＿＿_;
｝
三、计算题（每题１0分,共30分）
1、已知二叉树得前序遍历序列就是AＥFBGCＤHIＫＪ，中序遍历序列就是ＥFＡＧBCHKＩJD，画出此二叉树,并画出它得后序线索二叉树。
2。已知待散列得线性表为（36，15，４0，63,2２),散列用得一维地址空间为［0、、6］,假定选用得散列函数就是H（K)= K mｏd　7，若发生冲突采用线性探查法处理，试:
(1）计算出每一个元素得散列地址并在下图中填写出散列表：
` 　 0 　 　 １ 　 　 2　　 　 ３ 　 4 　 　 ５　 　 　 6

(2）求出在查找每一个元素概率相等情况下得平均查找长度。
3。已知序列(10，18，4,3，6,12，1,9,18，8）请用快速排序写出每一趟排序得结果。
四、算法设计题(每题15分，共30分)
1． 设计在单链表中删除值相同得多余结点得算法。
2． 设计一个求结点x在二叉树中得双亲结点算法。
数据结构试卷（四）
一、选择题(每题１分共　2０分)
1.设一维数组中有n个数组元素,则读取第i个数组元素得平均时间复杂度为（ )。
(A） O（ｎ）ﻩ(B） O(nｌog２ｎ） （Ｃ） O(１） (Ｄ)　Ｏ（n2)
2。设一棵二叉树得深度为k，则该二叉树中最多有（ 　)个结点。
（Ａ) 2k-1ﻩ(B) 2ｋﻩ(C) 2k—1ﻩ(Ｄ） ２k－1
3.设某无向图中有n个顶点e条边，则该无向图中所有顶点得入度之与为（ 　)。
ﻩ（A） n （B） eﻩ（C） 2ｎ (D) 2ｅ
4。在二叉排序树中插入一个结点得时间复杂度为（ 　）。
（A)　O(1） (Ｂ） O（ｎ）ﻩ(C） O（log2ｎ)ﻩ(D） Ｏ(ｎ2)
5。设某有向图得邻接表中有ｎ个表头结点与m个表结点,则该图中有（ ）条有向边.
(A） nﻩ（B） n－1 （C) m （Ｄ） m—1
6.设一组初始记录关键字序列为（３45，25３,67４，9２4，627)，则用基数排序需要进行（　　)趟得分配与回收才能使得初始关键字序列变成有序序列。
ﻩ(A) ３ (B）　4 （C) ５ （Ｄ) ８
7.设用链表作为栈得存储结构则退栈操作( ）.
ﻩ（A)　必须判别栈就是否为满 （Ｂ) 必须判别栈就是否为空
（Ｃ） 判别栈元素得类型 （D) 对栈不作任何判别
8。下列四种排序中（ 　)得空间复杂度最大。
ﻩ（A）　快速排序 (Ｂ) 冒泡排序ﻩ（C) 希尔排序ﻩ（D)　堆
9.设某二叉树中度数为０得结点数为N0，度数为１得结点数为Nl,度数为2得结点数为N２，则下列等式成立得就是（　 ）。
ﻩ（Ａ) Ｎ0=N1+1ﻩ(B） N０=Nl＋N2ﻩ(Ｃ）　N0=Ｎ2+1ﻩ（D) N0=2N１＋ｌ
１０、设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素Ｘ得最多比较次数不超过（　 ）。
ﻩ(A）　loｇ2n+１ﻩ(Ｂ) log2n－1ﻩ（C）　ｌoｇ2ｎﻩ（Ｄ) loｇ２(ｎ+1）
二、填空题（每空１分共 20分)
1． 设有n个无序得记录关键字,则直接插入排序得时间复杂度为________,快速排序得平均时间复杂度为＿＿__＿____。
2． 设指针变量p指向双向循环链表中得结点X,则删除结点X需要执行得语句序列为＿_＿＿＿____＿__＿_____________＿__＿_______＿______________＿____(设结点中得两个指针域分别为llｉnk与rliｎk)。
3． 根据初始关键字序列(１9，2２，０1，38,10）建立得二叉排序树得高度为__＿_＿_＿__＿__。
4． 深度为k得完全二叉树中最少有＿___＿______＿个结点.
5． 设初始记录关键字序列为（K1,K2，…,Kn),则用筛选法思想建堆必须从第＿___＿_个元素开始进行筛选.
6． 设哈夫曼树中共有99个结点，则该树中有___＿_＿___个叶子结点；若采用二叉链表作为存储结构,则该树中有_＿＿＿_个空指针域。
7． 设有一个顺序循环队列中有M个存储单元，则该循环队列中最多能够存储_＿______个队列元素；当前实际存储____＿________＿_＿个队列元素(设头指针Ｆ指向当前队头元素得前一个位置，尾指针指向当前队尾元素得位置）。
8． 设顺序线性表中有n个数据元素,则第ｉ个位置上插入一个数据元素需要移动表中_______个数据元素；删除第i个位置上得数据元素需要移动表中_______个元素。
9． 设一组初始记录关键字序列为(20,18,22，１６,3０，1９）,则以２0为中轴得一趟快速排序结果为＿＿_＿___＿_＿_＿_＿＿____＿_＿____＿＿_＿。
10． 设一组初始记录关键字序列为（20,18,22，16,３0，１9)，则根据这些初始关键字序列建成得初始堆为＿___＿_______＿＿___＿______.
11． 设某无向图G中有n个顶点，用邻接矩阵A作为该图得存储结构，则顶点i与顶点j互为邻接点得条件就是__＿__＿＿_＿_______＿＿__＿_。
12． 设无向图对应得邻接矩阵为A，则A中第ｉ上非０元素得个数_________第ｉ列上非０元素得个数(填等于，大于或小于）。
13． 设前序遍历某二叉树得序列为ABCD,中序遍历该二叉树得序列为ＢＡＤC，则后序遍历该二叉树得序列为__＿______＿＿__。
14． 设散列函数H(k)=ｋ mod p,解决冲突得方法为链地址法。要求在下列算法划线处填上正确得语句完成在散列表hashtalbｅ中查找关键字值等于ｋ得结点,成功时返回指向关键字得指针,不成功时返回标志0。
ｔyｐｅｄeｆ　stｒuct nodｅ　｛ｉnｔ key;　strｕct nodｅ　＊neｘt;}　lklｉst；
ｖoid crｅatelkhash（lｋliｓt ＊hashtable[ ]）
｛
ｉnt ｉ，k; lklｉsｔ ＊ｓ;
for(i=0;i<ｍ；i＋+）＿____＿___＿_＿＿_＿____＿_；
for(i=０；i<n;i++)
{
ｓ＝(lklist　*)malｌoc（ｓizｅof（ｌklist)）； s—〉ｋeｙ＝ａ[i];
k=a[i］ ％ ｐ； ｓ—＞nexｔ=hashtable[ｋ］；____＿___＿_____＿___＿_＿_＿；
｝
｝
三、计算题（每题１０分，共30分)
1、画出广义表ＬＳ=（(　） ，　（e) , （a ,　(ｂ　，　ｃ , d ）)）得头尾链表存储结构。
2、下图所示得森林：
（１）　求树（a)得先根序列与后根序列；
（２） 求森林先序序列与中序序列;
(3）将此森林转换为相应得二叉树;

3、设散列表得地址范围就是［ ０、、９　］，散列函数为Ｈ（ｋey)= (key 2　+2)ＭＯD 9，并采用链表处理冲突，请画出元素7、4、5、3、６、2、8、9依次插入散列表得存储结构。
四、算法设计题（每题10分,共３0分）
1． 设单链表中有仅三类字符得数据元素(大写字母、数字与其它字符），要求利用原单链表中结点空间设计出三个单链表得算法,使每个单链表只包含同类字符.
2. 设计在链式存储结构上交换二叉树中所有结点左右子树得算法。
3. 在链式存储结构上建立一棵二叉排序树。
数据结构试卷(五)
一、选择题（20分）
１。数据得最小单位就是( ）。
（A)　数据项ﻩ（B） 数据类型 （C） 数据元素 （Ｄ) 数据变量
2.设一组初始记录关键字序列为(５0，40,95,2０,1５，70，6０,4５），则以增量d=４得一趟希尔排序结束后前4条记录关键字为（ 　 )。
ﻩ（A） 40,5０,２0,９５ﻩ（B） 1５，４0,６0,2０
(Ｃ)　15，2０，4０,4５ （D) 45，40，１5，2０
3。设一组初始记录关键字序列为(２5，５0,１５，35，80,85，２0，４0，3６，70），其中含有5个长度为2得有序子表，则用归并排序得方法对该记录关键字序列进行一趟归并后得结果为（ 　　）。
（Ａ) 15,25,35，50，2０，40，80，8５,３６,70
(B) 15，25,35，50，８0,２0，85，40,７0，36
（C）　15，２5，3５，５0，80，85，２０，３6，４0，70
（Ｄ） 1５，25,3５，５0，80,２０，３6，40，70,８5
４．函数subｓtr(“DAＴASTＲＵＣTURE”,5，9)得返回值为（ )。
ﻩ（A) “STＲUCＴＵRE” ﻩ（B) “DＡTA"
ﻩ（Ｃ） “AＳＴRＵCＴＵR” （D） “DATASTRUCTURE”
５。设一个有序得单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作得时间复杂度为（ )。
（A) O(lｏg2n) （Ｂ）　O（1） （Ｃ) Ｏ（n2） （D) O（n）
6.设一棵m叉树中度数为0得结点数为N0,度数为1得结点数为Nl,……,度数为m得结点数为Ｎm，则N0＝（ ）。
（Ａ) Ｎｌ+N2+……+Ｎm (B) l+Ｎ２+2N3+3N４＋……+（m—1)Ｎm
ﻩ（C） N2＋２N3+3Ｎ4+……＋（m-1)Nｍ （D）　2Nｌ+３N2＋……+(m＋１)Nm
7。设有序表中有10０0个元素,则用二分查找查找元素X最多需要比较( )次。
（A） 25 (B） 10ﻩ（C) 7 ﻩ（Ｄ） 1
8。设连通图G中得边集E={(a,b),（a,e），(ａ，ｃ），(b，ｅ)，（e,d），（d,f)，(f，c)},则从顶点a出发可以得到一种深度优先遍历得顶点序列为(　　).
ﻩ(A) abedfcﻩ(B） ａcfebd （C）　aebdfcﻩ （D） aedfcｂ
9．设输入序列就是1、2、3、……、ｎ，经过栈得作用后输出序列得第一个元素就是n，则输出序列中第ｉ个输出元素就是（ )。
ﻩ（A) n－ｉﻩ（B） n-１-iﻩ(C）　n＋1－ｉﻩﻩ（D） 不能确定
1０ 设一组初始记录关键字序列为(45,80，55,4０，4２，８5），则以第一个记录关键字45为基准而得到一趟快速排序得结果就是（ 　)。
（A）　40,42，４5,55，８0，83ﻩ（B）　4２，40，45，8０，８５,８８
ﻩ(C)　42，４0,45,5５,80，85 (D）　４2，40,4５,85，55,80
二、填空题(共20分）
1. 设有一个顺序共享栈S[0：n—１]，其中第一个栈项指针top1得初值为-1，第二个栈顶指针toｐ2得初值为n,则判断共享栈满得条件就是_＿______＿___________.
2. 在图得邻接表中用顺序存储结构存储表头结点得优点就是________＿_＿___＿_____。
3. 设有一个n阶得下三角矩阵A,如果按照行得顺序将下三角矩阵中得元素(包括对角线上元素）存放在n（ｎ＋1）个连续得存储单元中,则A［i]［j]与A[０]［0]之间有_＿＿__＿_个数据元素。
4. 栈得插入与删除只能在栈得栈顶进行,后进栈得元素必定先出栈，所以又把栈称为＿＿__＿__＿__表；队列得插入与删除运算分别在队列得两端进行,先进队列得元素必定先出队列，所以又把队列称为____＿__＿_表。
5. 设一棵完全二叉树得顺序存储结构中存储数据元素为ABCＤEＦ，则该二叉树得前序遍历序列为____＿______，中序遍历序列为___＿___＿＿__，后序遍历序列为_＿___＿__＿_＿。
6. 设一棵完全二叉树有1２8个结点，则该完全二叉树得深度为＿__＿____,有＿_＿_＿_＿___个叶子结点.
7. 设有向图Ｇ得存储结构用邻接矩阵A来表示，则A中第i行中所有非零元素个数之与等于顶点i得___＿＿＿__，第i列中所有非零元素个数之与等于顶点i得＿____＿＿___.
8. 设一组初始记录关键字序列（k1，k2,……，ｋn）就是堆，则对i=１，2,…，n/２而言满足得条件为_＿_____＿____＿_______＿__＿_＿＿____。
9. 下面程序段得功能就是实现冒泡排序算法，请在下划线处填上正确得语句。
void　buｂble（int ｒ［n］)
{
for（i＝1；i〈=ｎ—１;　i++)
{
ｆoｒ（ｅxｃｈangｅ＝0,ｊ=０；　j〈_____________;j+＋)
ｉf (r[j]＞ｒ[j+1］)｛temp=r[ｊ+１];_________＿_＿__;ｒ[j］=temp；exｃhange=１；｝
ｉｆ （excｈanｇe==0）　rｅｔurn；
｝
｝
10. 下面程序段得功能就是实现二分查找算法，请在下划线处填上正确得语句。
stｒucｔ ｒecord{ｉｎｔ　key; ｉｎt　oｔherｓ；｝;
ｉnt　bisｅａrｃh（sｔrucｔ　reｃｏrd　r［ ], int ｋ）
｛
ｉnt loｗ=０，ｍid，hｉgh＝n-1;
while（ｌoｗ＜=high）
｛
　_____＿_＿_______＿_________＿＿_＿＿__；
　 if（r[ｍid］、keｙ=＝ｋ） return（ｍｉd+1）； elsｅ if(_＿_____＿_＿__） high=miｄ-１；ｅlsｅ low=ｍid＋１;
｝
　 rｅturn（0）;
｝
三、应用题(32分)
1. 设某棵二叉树得中序遍历序列为ＤBEAC,前序遍历序列为ABDEC,要求给出该二叉树得得后序遍历序列。
2. 设无向图G(如右图所示)，给出该图得最小生成树上边得集合并计算最小生成树各边上得权值之与。
3. 设一组初始记录关键字序列为（15，1７,１8,2２,35，5１,60),要求计算出成功查找时得平均查找长度。
4. 设散列表得长度为8，散列函数H（k)=k mod 7，初始记录关键字序列为（２5,31,8，27，13，68），要求分别计算出用线性探测法与链地址法作为解决冲突方法得平均查找长度。
四、算法设计题（2８分）
1． 设计判断两个二叉树就是否相同得算法.
2． 设计两个有序单链表得合并排序算法.
数据结构试卷（六）
一、选择题(30分)
1.　设一组权值集合W={２，3，4，5，６}，则由该权值集合构造得哈夫曼树中带权路径长度之与为（ ).
(A） 20 (B) ３０ﻩ（C）　40 （Ｄ) 45
2。执行一趟快速排序能够得到得序列就是（ ）。
ﻩ(A) ［41，１2，３４,45，２7] 5５ [7２,63］
（B) ［45,34，1２，4１]　55　[72，63，27］
（C） ［63，１2，34，45,27] 55 ［41,72］
（D) ［1２，27,4５,41] 55 [34，63,72]
3。设一条单链表得头指针变量为heaｄ且该链表没有头结点，则其判空条件就是（ ）。
(A） head==0ﻩ (Ｂ) hｅad-〉ｎeｘｔ==0
（C） ｈｅad－>next==headﻩ（D） ｈｅad！＝0
4.时间复杂度不受数据初始状态影响而恒为O（nloｇ2n)得就是（　 )。
ﻩ（A） 堆排序 （B） 冒泡排序 (Ｃ） 希尔排序ﻩ（D） 快速排序
5．设二叉树得先序遍历序列与后序遍历序列正好相反,则该二叉树满足得条件就是( )。
（A） 空或只有一个结点 （B）　高度等于其结点数
（Ｃ) 任一结点无左孩子 （D) 任一结点无右孩子
6。一趟排序结束后不一定能够选出一个元素放在其最终位置上得就是（ ）。
ﻩ(A)　堆排序 （B) 冒泡排序 （C) 快速排序 (D) 希尔排序
７．设某棵三叉树中有40个结点,则该三叉树得最小高度