数据结构试卷A.doc

专业班级: 姓名: 学号:
…………………………密………………………………封………………………………线…………………………
河南理工大学万方学院 200６-200７学年第　　2　学期
专业班级: 姓名: 学号:
…………………………密………………………………封………………………………线…………………………
《数据结构》试卷(Ａ卷）
考试方式： 闭卷 　 　　 　 本试卷考试分数占学生总评成绩得　 8０ ％
总 分

题号
一
二
三
四
核分人

得分

　 复查总分　　 　　 　　 　 　 总复查人 　 　　
得分
评卷人

毋小省
一、单选题(本题得每一备选答案中,只有一个就是正确得，请把您认为正确得答案得题号填入题干得括号内，每小题２分，共30分）
1、 若长度为ｎ得线性表采用顺序存储结构,在其第i个位置插入一个新元素得算法得时间复杂度为( ）。（1≤i≤n+１）
（1） O（0） （2) O(１）　 　（3) O（n） 　 　（4）　O（n２）
2、在单链表中ｐ所指结点后插入s所指结点，则下列语句正确得就是（ 　)
(1)　p→next=s； ｓ→nｅｘt=p； 　 　　　 　 （２） s→ｎext=p→next； p→nｅxt=s；
　（３） s→nexｔ＝p； p→next=s； 　 　 　 (4） ｐ→ｎext=s→next；　s→ｎｅｘｔ＝p;
3、 设一个栈得输入序列为A,B,Ｃ,D,则借助一个栈所得到得输出序列不可能就是（ 　)
(1）A,B，C,Ｄ 　 （2）D,Ｃ，B，A (3)A，C，D,B 　 　（4）Ｄ，A，B,C
4、若由树林转化得到得二叉树就是非空得二叉树，则二叉树形状就是(　　 )
(1) 根结点无右子树得二叉树 　 　 　　　　 　 (2) 根结点无左子树得二叉树
(3） 根结点可能有左二叉树与右二叉树 （４）　根结点只有一个孩子结点得二叉树
5.设二叉树得根为第一层，则深度为ｉ得二叉树结点数最多为( )
（1)２i 　 （2） ２i　＋1 　 （3）2i　—１ 　ﻩ(4）2ｉ －1
6、 首先访问结点得左子树,然后访问该结点,最后访问结点得右子树，这种遍历称为（　　　）
（1）前序遍历 　(2）后序遍历 （3）中序遍历 　 （４）层次遍历
7。给定下列有向图，从顶点1出发,其广度优先搜索序列为（ 　）
（1）12534 （2）1243５ (３) 14325 　 （4）1２345

8.散列表中得冲突就是指（　 ）
（１）  两个元素具有相同得序号 （2) 两个元素得关键字相同,而其她属性相同
(３）　不同得关键字对应相同得存储地址 　　 （４） 数据元素得地址相同
9、 线性表若采用链式存储结构时,要求内存中可用存储单元得地址：（ 　）
（1）必须就是连续得 　 (2)部分地址必须就是连续得
（3）一定就是不连续得 　 　 　（４)连续或不连续都可以
１０.下面程序段得时间复杂度为（　 ）
fｏｒ (int　i=1;i＜m；i+＋)
　 　 for　(int j=1;j<n；j++）
　　　　 　 　ａ[ｉ］[j]=ｉ＊j;
　 （１) Ｏ(m２) (2)　Ｏ(n２） 　　 （3） Ｏ(ｍ*n） 　 （4） O(m+ｎ)
１1．当利用大小位得数组顺序存储一个队列时，该队列得最大长度为（　 ）
(1）n-２　 （２）　n-1 　　 　（３) n 　 　 　(４)ｎ＋1
1２.对线性表进行折半搜索时，要求线性表必须( 　)
（１）顺序存储　　 　　 　　 （2)顺序存储且结点按关键字有序
（３）链式存储 　 (4)链式存储且结点按关键字有序
13。采用线性探查法解决冲突时所产生得一系列后续地址( )
(１）必须大于等于原散列地址 　 　 　 （2）必须小于等于原散列地址
（3)可以大于或小于但不等于原散列地址 （4） 对地址在何处没有限制
14．栈得插入与删除操作在(　 ）进行。
（1)栈顶 　 　 （2)栈底　 　 (3)任意位置 　 　(4）指定位置
15.在一个顺序存储得循环队列中,对头指针指向队列得（　 )位置。
（1)前一个 　(2)后一个 　 　 (3)当前 　 （4）后面
得分
评卷人

毋小省
二、填空题（每空1分，共20分)
1、数据得逻辑结构被分为＿__０_＿＿＿_＿＿___，＿_________＿_____,_________＿_＿_＿___,___________＿＿_＿＿。
２、单链表与循环链表得区别就是__＿________＿____＿_＿_____＿＿_____。
3、在一个循环队列中，判断对空得条件就是串就是＿__＿_＿______＿_＿__＿__，判断对满得条件就是串就是＿＿＿____________＿＿_＿____________
4、 从有序表（12，18，30，43，56,78，82,95）中一次折半搜索４3与56元素就是,其比较次数分别为_＿＿___＿与_______.
５、与哈西表得平均查找长度有关得三个因素分别就是_＿＿_＿_＿_＿____________________，___＿＿＿＿__＿___＿______　,__＿___＿__＿_＿____＿__＿_。
6、对于一个具有ｎ个顶点与e条边得连通图,其生成树中得顶点数个边数分别为_＿_______与_＿__＿＿____。
７、在二叉排序树中，左子树所有结点得关键字值都＿____＿_＿该结点得关键码值,而右子树中所有结点得关键字值都_________该结点得关键码值.
8、在一个小顶堆中，堆顶元素得值就是所有结点中得＿_＿____＿______,在一个大顶堆中，堆顶元素得值就是所有结点中得＿_＿___＿＿___＿_＿.
9、假定一组纪录得关键字为(４6，79,56,３8，40,80），对其进行快速排序得一次划分得结果为__＿＿_____＿_________＿__＿____＿___＿_＿。
１０、在一个网络得所有生成树中,各边权值之与最小得生成树，称为该网络得_______＿＿_____。
得分
评卷人

毋小省
三、判断题（判断下列各题就是否正确,若正确在（)内打“√"，否则“×”。每小题1分，共10分)
（ 　　）1、 栈与队列得存储方式既可就是顺序方式，也可就是链接方式。
（ )２、 顺序表结构适宜于进行顺序存取,而链表适宜于进行随机存取。
（     )3、二叉树中任何一个结点得度都就是2。
(     ）4、有回路得有向图不能完成拓扑排序。
（　 　)5、按先根次序遍历森林等同于按先序法遍历对应得二叉树.
（     )６、n（ｎ〉1)个顶点得无向连通图最少由n-1条边。
（ 　 )7、有向图得邻接表表示中边表中结点得总数与有向图中有向边得条数相等。
（     ）8、一个无向图得邻接矩阵中各元素之与与图中边得条数相等。
（ 　 ）9、归并排序要求待排序文件已部分排序。
( 　）１０、顺序检索时数据得存储方式可以就是顺序得，也可以就是链接得。
得分
评卷人

毋小省
四、综合题(共40分)
１．已知某系统在通信联络中只可能出现8种字符，其概率分别为0、0５,０、29,0、0７，0、0８,0、１４，0、23，0、0３，０、11，试设计哈夫曼编码.（7分）
２.设待排序得记录得关键字序列为｛12，2，１6，30,10，2０，１8}，写出使用链式基数排序每趟得结果.（6分）
3、拓扑排序得结果不就是唯一得，对于下图得结点进行拓扑排序，试写出其中得任意5个。
（5分）
V1
V3
V4
V6
V5
V7
V8
V9
V2

A

4．分别按前序、后序、对称序列写出下图二叉树得结点，并转化为树林,分别按先根次序、后根次序列出其结点。（6分)
I
F
D
E
A
B
C
G
H

5、已知一组关键字为（19，14,23，01，68，20,84，2７,55,11,10，７9）,则按哈希函数H（kｅy)=ｋey MＯＤ 13，表长为１３,分别用线性探查法与链地址法处理冲突构造哈希表,并计算各平均查找长度。（10分）
６、程序填空(6分)
对有序表R[０]至R[n－1］进行二分查找，成功时返回记录在表中得位置，失败时返回0、
Stｒuct　sqlisｔ
｛　keytype　key;
}；　
ｉnt　binsｒch（sｑlist R[ ]，kｅｙtypｅ k）
　/／在表R中查找关键字k
｛ inｔ low ，hiｇh,mｉd；
lｏｗ＝0; ｈｉｇh=n-1；
　whiｌe（ 　 　 　 　 ）
　 mid＝(loｗ＋high）／2;
　 if　(k==Ｒ[mｉd]、key）　 ｒeturｎ　 mid；
　 　 ｅlse if（　ｋ<R[mid]、keｙ )
　 　　 　 　 　 ；
　 　 　 　　 　　　　　 　 ｅlｓe　　 　　 　 ；
　 　 　 　 ｝
　 　return ０；
}