数据结构复习题及答案.doc

一、选择题。（每小题2分，共4０分)
（1) 计算机识别、存储与加工处理得对象被统称为＿___A_＿__。
Ａ、数据ﻩ 　　 B、数据元素 　　 ﻩ
C、数据结构 　D、数据类型
(2) 数据结构通常就是研究数据得____　A __＿__及它们之间得联系。
A、存储与逻辑结构　 Ｂ、存储与抽象
Ｃ、理想与抽象 　 D、理想与逻辑
（3） 不就是数据得逻辑结构就是____ A　____＿_。
A、散列结构 　 　 B、线性结构　　 　
C、树结构 　 　 D、图结构　
(4）　数据结构被形式地定义为<D,R〉，其中D就是__＿_ B _____得有限集，R就是____ C ___＿_得有限集。
Ａ、算法　 　　 　 　　　 B、数据元素
Ｃ、数据操作 　 　 　　 　 D、逻辑结构
(５)　组成数据得基本单位就是__＿_ A _＿____.　
A、数据项ﻩ　　 　 　　 Ｂ、数据类型
C、数据元素ﻩ　 　 　 　 D、数据变量
（6） 设数据结构Ａ=(D，Ｒ）,其中D={1，2,３，4｝,R={r｝，r={＜１，２〉，<2，3>,〈3，4〉,<4，1〉｝，则数据结构A就是___＿ A ______.
A、线性结构 　　 　 　 　 B、树型结构
C、图型结构ﻩ 　 　 　 　　 D、集合
(7) 数据在计算机存储器内表示时,物理地址与逻辑地址相同并且就是连续得，称之为＿__ C __＿_.
Ａ、存储结构 　 　 　 　 　B、逻辑结构 　
Ｃ、顺序存储结构 　 　 　 　 D、链式存储结构
（8） 在数据结构得讨论中把数据结构从逻辑上分为___ A __＿＿。
Ａ、内部结构与外部结构 　　　Ｂ、静态结构与动态结构
Ｃ、线性结构与非线性结构ﻩ D、紧凑结构与非紧凑结构
（9） 对一个算法得评价,不包括如下____　B _＿＿__方面得内容。
A、健壮性与可读性 　B、并行性
Ｃ、正确性　　 　　 　 　 　　D、时空复杂度
（1０)　算法分析得两个方面就是__ A　____。
A、空间复杂性与时间复杂性　 B、正确性与简明性
C、可读性与文档性 　 　 　　D、数据复杂性与程序复杂性
（11)　线性表就是具有ｎ个_＿_ C _____得有限序列（n≠0）。
A、表元素　 　　　　　 　　B、字符
C、数据元素 　 D、数据项
(12)　线性表得存储结构就是一种____ Ｂ　__＿_得存储结构。
A、随机存取 　　　 　 　B、顺序存取
C、索引存取 　 　 D、HASH存取
（13） 在一个长度为n 得顺序表中,向第i个元素(1≤ i≤ n+1）之前插入一个新元素时，需要向后移动____ B __＿_个元素。
A、n－ｉ 　 　 　 B、n—i+1 　
C、n-i—1 　 　　 　 　 　 　 D、i
（1４）　链表就是一种采用＿___　B _＿＿_存储结构存储得线性表;
Ａ、顺序　 　 　 　 B、链式
C、星式 　 　　 　 Ｄ、网状
(15） 下面关于线性表得叙述错误得就是＿_＿ D　_____.
A、线性表采用顺序存储必须占用一片连续得存储空间ﻩ
B、线性表采用链式存储不必占用一片连续得存储空间
C、线性表采用链式存储便于插入与删除操作得实现
D、线性表采用顺序存储便于插入与删除操作得实现
（16）　设指针q指向单链表中结点A,指针p指向单链表中结点A得后继结点Ｂ，指针s指向被插入得结点X,则在结点A与结点B之间插入结点X得操作序列为_＿ Ｂ ____＿_.
A、 s—〉next＝p->nｅｘt;p—＞neｘｔ=-s;ﻩ
Ｂ、 ｑ－>next=ｓ；　s—>nｅxt=p;
C、 p->ｎｅxt=s—＞ｎext；s—＞ｎext=p;
D、 p—＞ｎext=s；s-〉next=q;
(１7） 设指针变量p指向单链表结点Ａ，则删除结点A得后继结点Ｂ需要得操作为＿__　A　__＿＿＿。
ﻩA、 ｐ-〉ｎext＝ｐ—〉neｘｔ—＞ｎextﻩ　 　 B、 p=ｐ-＞next
ﻩC、 p＝p->ｎｅxt－＞nｅxt 　 　D、 p->ｎexｔ=p
（１８） 下列说法哪个正确？＿___　D　__＿_＿＿ 
A、 堆栈就是在两端操作、先进后出得线性表
B、　堆栈就是在一端操作、先进先出得线性表
Ｃ、　队列就是在一端操作、先进先出得线性表
Ｄ、 队列就是在两端操作、先进先出得线性表
（1９） 栈与队列得共同点就是 __＿_＿ Ｃ _____＿＿。
A、 都就是先进后出 　 　　　　 　 B、　都就是先进先出
C、 只允许在端点处插入与删除元素 　Ｄ、　没有共同点
（20） 栈与一般线性表得区别主要在＿＿_＿_D_＿_＿__。
Ａ、元素个数 　 Ｂ、元素类型 　 C、逻辑结构　 　 D、插入、删除元素得位置
（21）　链栈与顺序栈相比，比较明显得优点就是__＿__D__＿＿_。
A、插入操作更加方便 　　 　B、删除操作更加方便
C、不会出现下溢得情况 　Ｄ、不会出现上溢得情况
（22) 以下数据结构中哪一个就是非线性结构＿__　D _＿___＿。
A、队列     Ｂ、栈      C、线性表      D、二叉树 
（23) 若已知一个栈得入栈序列就是1,2,３，…，n，其输出序列为p1，p2,p3,…，pn，若p1=n，则pi为 _____ Ｃ　__＿___.
A、 i    B、 B、 n=i      C、 ｎ－i+1     D、不确定
(2４) 当利用大小为Ｎ得一维数组顺序存储一个栈时,假定用top==N表示栈空，则向这个栈插入一个元素时,首先应执行  _＿__　B _＿____语句修改ｔoｐ指针。
A、　top++     B、 tｏp－－     C、 top=0     D、 ｔop
（25)　 4个元素进Ｓ栈得顺序就是Ａ,B,C，Ｄ,经运算POP（S）后，栈顶元素就是___ C _＿_____。
A、　A    Ｂ、　Ｂ     C、 C     D、 D
（26） 一个栈得输入序列就是ａ，b,c，d，e,则栈得不可能得输出序列就是__＿_ C ____＿。
Ａ、 ｅdcba    Ｂ、 decba     C、　ｄceab     Ｄ、 abcde
(27）　设输入序列就是1、2、３、……、n，经过栈得作用后输出序列得第一个元素就是ｎ，则输出序列中第i个输出元素就是____ C ＿_____。
A、　n－i    B、 ｎ—１－ｉ     C、　n＋1-i     D、不能确定
（2８） 字符A、Ｂ、Ｃ、Ｄ依次进入一个栈，按出栈得先后顺序组成不同得字符串，至多可以组成＿__ Ｂ _＿_个不同得字符串？
A、 １５    B、 1４     C、 16     Ｄ、 21
（２９） 设指针变量top指向当前链式栈得栈顶，则删除栈顶元素得操作序列为____ D ＿__＿___.
A、 top=top+1；       B、 ｔop=ｔop-1;   
C、 top－>next＝ｔoｐ;   　　　D、 ｔｏp=top—>nｅxｔ；
（3０）　设栈S与队列Ｑ得初始状态为空，元素E1、Ｅ2、E３、E4、E5与E6依次通过栈Ｓ,一个元素出栈后即进入队列Q，若6个元素出列得顺序为E2、E4、E3、E６、E5与E1，则栈S得容量至少应该就是_＿__ C　_____.
Ａ、 6    B、　４     C、 3     D、 ２
(３1) 若用一个大小为6得数组来实现循环队列，且当前reａr与fｒｏnｔ得值分别为0与3。当从队列中删除一个元素，再加入两个元素后,reａｒ与froｎt得值分别为 ____ Ｂ ＿＿_＿＿。
Ａ、 1与5    Ｂ、 2与4     C、 4与2     D、 5与1
(3２） 设顺序循环队列Q[0：Ｍ-1]得头指针与尾指针分别为F与Ｒ,头指针F总就是指向队头元素得前一位置,尾指针R总就是指向队尾元素得当前位置，则该循环队列中得元素个数为___＿ C ＿_＿__.
A、　R-F    B、 F－R     C、　（R—F+M)％Ｍ     Ｄ、　（Ｆ-Ｒ＋M)％M  
(33)　设指针变量ｆｒont表示链式队列得队头指针，指针变量reａｒ表示链式队列得队尾指针,指针变量s指向将要入队列得结点X,则入队列得操作序列为 __＿_ Ｃ __＿__.
A、 ｆrｏnt－〉neｘt=s;ｆront=s;    B、 s->nexｔ=ｒear；rear=s;  
C、 rｅaｒ－＞nｅｘｔ=s；rｅar＝s;     Ｄ、 s-〉next=ｆｒont；front=ｓ;
(34）　 如下陈述中正确得就是__＿ A ______。
A、 串就是一种特殊得线性表      Ｂ、 串得长度必须大于零  
Ｃ、　串中元素只能就是字母       D、　空串就就是空白串
（3５） 下列关于串得叙述中,正确得就是 _＿_　Ｄ _＿＿___。
A、 串长度就是指串中不同字符得个数       B、 串就是n个字母得有限序列
C、 如果两个串含有相同得字符,则它们相等    
D、　只有当两个串得长度相等,并且各个对应位置得字符都相符时才相等
（36）  字符串得长度就是指＿__ C _＿____。
A、　串中不同字符得个数      B、 串中不同字母得个数  
C、 串中所含字符得个数      D、 串中不同数字得个数
（37） 两个字符串相等得充要条件就是_＿＿＿ Ｃ ＿_____.
A、 两个字符串得长度相等       Ｂ、 两个字符串中对应位置上得字符相等
C、 同时具备（A）与(B)两个条件     D、 以上答案都不对
(３8) 串就是一种特殊得线性表，其特殊性体现在____ Ｂ ____＿＿_。
Ａ、 可以顺序存储      B、　数据元素就是一个字符
C、 可以链接存储      Ｄ、　数据元素可以就是多个字符
（39）　　设有两个串p与q,求ｑ在ｐ中首次出现得位置得运算称作 __＿_　Ｂ _____＿。
A、　连接    B、 模式匹配     C、 求子串     D、 求串长
（４0) 设串sI="ＡＢCDEFG”，s２=”ＰQＲST"，函数ｃon(x，y）返回ｘ与y串得连接串,suｂｓ（s,i,j）返回串ｓ得从序号ｉ得字符开始得j个字符组成得子串，leｎ(ｓ）返回串s得长度，则con(subs（s1，2,１en（s2））,ｓｕｂs（sl，len(s2)，2））得结果串就是__ D ＿＿_。
A、 ＢＣDEＦ     Ｂ、 BCDEFＧ     C、　BCPQRＳT     D、 ＢCＤEFＥF
(41)　 函数subｓtr（“DAＴASTRUCTUＲE”，5,９）得返回值为___　A　___＿__。
A、 “ＳTRＵＣＴＵRE”    Ｂ、 “DＡTＡ"    C、 “ASＴＲUCTＵＲ”    D、 “ＤAＴASTRUCTUＲE"
（42) 设串S=”I AM A TＥACHＥR！",其长度就是_＿＿＿　D ____＿_。
Ａ、　16    B、 １1     C、 １4     D、 １5  
(4３） 假定在一棵二叉树中,双分支结点数为15个，单分支结点数为３2个,则叶子结点数为____B____。　
A、 15 　 　　 Ｂ、 16 　　　　 C、　１7 D、 4７
(44）　 假定一棵二叉树得结点数为18个,则它得最小高度____B____。
A、　４ 　 　B、 5　 　 　　　 C、　６　 　 　D、　18
(4５）　 在一棵二叉树中第五层上得结点数最多为____C＿___。
A、 ８ 　 Ｂ、　15　 　 　 C、 16 　 Ｄ、 32
(46) 　在一棵具有五层得满二叉树中，结点总数为____A____。
A、 ３1　 　 B、 ３2 　　 C、 ３3 　 　 　　 Ｄ、 16
(４７） 已知８个数据元素为（34、７6、４5、18、26、54、92、65),按照依次插入结点得方法生成一棵二叉排序树后,最后两层上得结点总数为____B____.
A、 1 　 　 　 　B、　2　　 　 　 Ｃ、 　 Ｄ、　4
（48） 由分别带权为9、2、５、7得四个叶子结点构造一棵哈夫曼树，该树得带权路径长度为___＿C__＿_。
A、　23 　 Ｂ、 ３７ 　 C、 4４ 　 　 D、 46
（49） 在树中除根结点外,其余结点分成m (m≥0)个___＿A ____得集合Ｔ1，T2，T３、、、Ｔm，每个集合又都就是树，此时结点T称为Ti得父结点,Ti称为T得子结点（１≤i≤ｍ）.
A、　互不相交 　 　 　 B、 可以相交 　　
C、 叶结点可以相交 　 　Ｄ、 树枝结点可以相交
(５0） 如果结点A有三个兄弟，而且B就是A得双亲，则B得出度就是_＿__B_＿__.
A、　３ 　 　 　B、 4 　 C、 5 　 　 Ｄ、 1
（51) 　在一个有向图中,所有顶点得入度之与等于所有顶点得出度之与得____B_＿_＿倍。
A、 1/2 　 　 　 B、 1　 　　　 　C、 2 　 D、 4
(5２)　 具有n个顶点得无向完全图,边得总数为_＿＿_　D____条。
A、 n-1 　 　 B、　n　 　 Ｃ、　n+１ 　　　 　　　 D、 n＊（n—1）/２
（５3） 在无向图G得邻接矩阵A中，若A［ｉ，j］等于1，则Ａ[j，i]等于_＿＿_C ＿___。
A、　i+j 　　B、 i-j 　 　 　 C、 １ 　 　 　 D、 0
（54）　 图得深度优先或广度优先遍历得空间复杂性均为____A_＿__ 。（访问标志位数组空间)
A、 O（n） 　　 　 　 B、　O（e） 　 C、 O(n—e) 　 D、 O（n+ｅ)
（55)　 请指出在顺序表{2、5、7、1０、14、1５、18、23、35、41、5２}中，用折半法查找关键码12需做____　C ___次关键码比较。
A、2　 　 Ｂ、3　 　 C、4 　　 D、５
（56） 对线性表进行折半查找时，必须要求线性表　＿___ C __＿_。
A、 以顺序方式存储　 　 　　　　 B、 　以链接方式存储
Ｃ、 以顺序方式存储，且结点按关键字有序排列
D、 　以链接方式存储，且结点按关键字有序排列
(57） 设二叉排序树中有n个结点，则在二叉排序树得平均查找长度为__＿ Ｂ　__＿__。
A、 O(1）　 　 ﻩB、 O（ｌog２ｎ) 　　 　C、 Ｏ（n） D、 O(n２)
（58) 依次插入序列(５0，７２,4３,85，75，２0，３5，45，65，30）后建立得二叉搜索树中，查找元素3５要进行_＿ A　＿__元素间得比较.
A、4次 ﻩﻩﻩB、５次ﻩ ﻩﻩＣ、７次ﻩ ﻩD、１0次
（5９） 设散列表中有m个存储单元,散列函数H（key）=　kｅy % p,则p最好选择___ B　__＿＿_.
A、 小于等于ｍ得最大奇数ﻩﻩB、 小于等于m得最大素数
C、　小于等于m得最大偶数ﻩﻩD、　小于等于ｍ得最大合数
（６0）　 ＿___ D ____＿就是HASH查找得冲突处理方法.
A、求余法 　 B、 平方取中法 Ｃ、 二分法　 D、 开放地址法
(61) 当α得值较小时,散列存储通常比其她存储方式具有____＿　Ｂ _＿____得查找速度.
A、 较慢ﻩ ﻩＢ、 较快ﻩﻩ C、　相同　 　 Ｄ、　不确定
(６2) 　对线性表进行折半查找最方便得存储结构就是_＿__ B ___＿___。
A.顺序表　　　　　 　 　Ｂ。有序得顺序表
C．链表　 　 　 　 D.有序得链表
(6３） 　如果要求一个线性表既能较快得查找,又能适应动态变化得要求，可以采用_＿___ D ____查找方法。
Ａ．分块 　 　B.顺序　　 　 C。折半 　 　 　 　D.散列
(64） 散列函数有一个共同性质，即函数值应按___　Ｃ　＿__＿_＿取其值域得每一个值.
A.最大概率 　 B。最小概率　 C．同等概率 　 D.平均概率
(６5) 下述排序算法中，稳定得就是___ B __＿__。
A、直接选择排序　　 B、 直接插入排序 　C、快速排序 D、堆排序
(６6)　　下列排序算法中，＿_＿_ A　____需要得辅助存储空间最大。
A、快速排序ﻩﻩB、插入排序 C、希尔排序ﻩ D、基数排序
（６7) 下列各种排序算法中平均时间复杂度为O（n2)就是＿__ D _＿___。
A、 快速排序 　　 B、 堆排序 ﻩC、　归并排序 　D、 冒泡排序
(68) 在基于关键码比较得排序算法中,____ C ＿_＿__算法在最坏情况下，关键码比较次数不高于O(nlog2ｎ)。
A、 起泡排序ﻩﻩﻩ Ｂ、 直接插入排序ﻩ
C、 二路归并排序 D、 快速排序
(69) 　一组记录为{４6，７9，56,３8，84,40}，则采用冒泡排序法按升序排列时第一趟排序结果就是＿__ Ｂ _____　.
A、 46，７9,56，38,４0,84 B、46，56，38，７９，４0,８4
Ｃ、 ３8,４0,４6，56，84,7９　 　 　D、38,46，79，５6，4０，84
(7０）　　每次从无序表中取出一个元素,把它插入到有序表中得适当位置,此种排序方法叫做___ Ａ　＿____ 排序。
A、 插入 B、 堆 　　 　　 Ｃ、快速 　 D、归并
(7１)　　每次从无序表中挑选出一个最小或最大元素，把它交换到有序表得一端,此种排序方法叫做__＿ B　_＿＿_＿排序。
A、　插入 　 　　Ｂ、 堆　 　　　 Ｃ、快速 　　　 D、归并
（7２） 设一组初始记录关键字序列(5，２,6，3，8）,以第一个记录关键字5为基准进行一趟快速排序得结果为___＿ Ｃ ＿___。
A、 2,3,5,8，6 B、 3,2,5,8，6
ﻩＣ、 3,２，５,６，8ﻩ D、　2，３,6,５，８
(73)　 下列排序方法中,哪一种方法得比较次数与纪录得初始排列状态无关_＿_　D _____.
Ａ、 直接插入排序　 　 　Ｂ、 起泡排序
C、　快速排序 　 　 Ｄ、 直接选择排序
（7４) 设有关键码初始序列{Ｑ，H，C，Y，P，A，M，S，R,D,F，X｝，新序列｛F，H,C,D，P,A,M，Ｑ,Ｒ，S，Y,X}就是采用＿＿__ C _＿__ 方法对初始序列进行第一趟扫描得结果.
Ａ、 直接插入排序 　 　 　Ｂ．二路归并排序
C。以第一元素为分界元素得快速排序　 　 D。基数排序
（７5） 在待排序文件已基本有序得前提下,下述排序方法中效率最高得就是＿_ Ｃ _＿__.
A、 　 直接插入排序 　 B、　　直接选择排序
C。 快速排序 　　 　 　 D。 　归并排序
（76） 若需在O（nlog2n）得时间内完成对数组得排序，且要求排序就是稳定得,则可选排序方法就是＿__ C ___＿＿ 。
Ａ、 　　快速排序　 B。　 堆排序
Ｃ．　 归并排序 　D。　 直接插入排序
（７7） 将两个各有ｎ个元素得有序表归并成一个有序表,其最少得比较次数就是___ B ＿____＿_。
A。 n 　 B． 2n—1 C。 　２n 　 　 D。 　n-1
(78） 下列排序算法中，＿___ C ＿_＿_ 算法可能会出现下面情况：初始数据有序时，花费得间反而最多。
A、　 　堆排序 Ｂ．冒泡排序 　 C.快速排序 　 　 D。 ＳHＥＬL排序
二、填空题。（每空1分,共１0分)
（1) 数据结构就是一门研究非数值计算得程序设计问题中计算机得　 　 数据 　 　 以及它们之间得 关系 　 　 与运算等得学科。
(２） 数据结构包括数据得ﻩ逻辑结构ﻩ 结构与ﻩﻩ物理结构 结构.
（3) 数据结构从逻辑上划分为三种基本类型：___＿线性数据结构__＿＿_＿＿、___＿树型结构__＿＿＿_与___＿_图结构______。
（４) 数据得物理结构被分为___顺序存储＿_____、___链式存储_____、____索引存储____＿＿与＿____＿散列表（Hash)存储___＿_四种。
（5） 一种抽象数据类型包括＿__＿_变量得取值范围_____与　____操作得类别_＿___两个部分.
(6) 数据得逻辑结构就是指 　　 数据元素间得逻辑关系 　 　 　，数据得存储结构就是指　 　 　 数据元素存储方式或者数据元素得物理关系 　　 　 　。
（7） 数据结构就是指数据及其相互之间得____关系___＿_＿____。当结点之间存在M对N（M：N）得联系时，称这种结构为＿_____＿_网状结构_＿___＿_＿。当结点之间存在1对N(1：Ｎ）得联系时，称这种结构为_____树结构＿___＿_____。
（8)　对算法从时间与空间两方面进行度量，分别称为 　 空间复杂度与时间复杂度　 　 　　 　 　 分析。
（9） 算法得效率可分为＿_＿___空间__＿___＿＿_效率与_＿＿___时间＿____＿_＿_效率。
（１0)　for（ｉ=1,ｔ=1,s=0;i〈＝n；i+＋) {t＝t＊i；s=ｓ+t;}得时间复杂度为___Ο（ｎ)_____＿。
(11） 线性表就是n个元素得___＿＿＿＿＿＿有限序列＿_______＿_____＿_＿＿__。
（12） 线性表得存储结构有______＿__顺序存储与链式存储________＿__________＿。
(13） 设线性表中有n个数据元素,则在顺序存储结构上实现顺序查找得平均时间复杂度为＿__＿_O（n)_____＿，在链式存储结构上实现顺序查找得平均时间复杂度为__＿_ O(ｎ）____＿_＿。
（1４） 设顺序线性表中有ｎ个数据元素，则第i个位置上插入一个数据元素需要移动表中___ ｎ-i＋１__＿_个数据元素;删除第i个位置上得数据元素需要移动表中___ n-i　____个元素。
（15) 若频繁地对线性表进行插入与删除操作，该线性表应采用_＿＿__链式_________存储结构。
(１６)　链式存储结构中得结点包含＿_____数据_________＿域与_＿＿__指针_＿________域.
（17） 对于一个长度为n得单链存储得线性表,在表头插入元素得时间复杂度为___Ο(1）_＿＿___,在表尾插入元素得时间复杂度为_____Ο（n)_＿＿＿___。
（１8)　栈得插入与删除只能在栈得栈顶进行,后进栈得元素必定先出栈，所以又把栈称为____ ＦＩＬO ________表;队列得插入与删除运算分别在队列得两端进行,先进队列得元素必定先出队列,所以又把队列称为 __＿__　ＦIFO ____＿_表.
（19） s=" I am　ａ　ｍan” 长度为＿_＿_10＿＿____＿ 。
(20)　　s1＝”hellｏ “，ｓ2＝"boy",s1，ｓ２连接后为：_＿______　heｌlo　bｏｙ　____________＿＿ .
(21) 　ｓ＝”thiｓ ｉs　the　mａin strｉng"，sub＝"string",stｒｉnｄex(s，sub）就是:＿＿＿___＿13＿____＿_.
（22）　 ｉnｔ a［10］[10］，已知a=1000，sｉzeof(int)=2,求ａ［３]［3］地址:＿_____＿106６___＿__＿_＿__ 。
(２3） 设有两个串p与q,求q在p中首次出现得位置得运算称为__＿＿____模式匹配____＿___。
(2４) 在树型结构中,树根结点没有＿__＿__前趋＿_____结点，其余每个结点有且仅有__＿___一＿_＿__＿个前驱结点；树叶结点没有__＿_＿_后继__＿＿_＿结点,其余每个结点得______后继___＿__结点数不受限制。
（25） 在一棵二叉树中,度为0得结点得个数为ｎ0 ,度为2得结点得个数为n２ ,则：ｎ0 =___＿__n2 +１＿___＿_.
（2６) 由分别带权为3,9,6,2，５得共五个叶子结点构成一棵哈夫曼树,则带权路径长度为＿＿___＿　55_＿____。
（27) 在图G得邻接表表示中,每个顶点邻接表中所含得结点数,对于无向图来说等于该 顶点得　＿__＿＿_度数___＿__,对于有向图来说等于该顶点得_____＿出度数_＿_＿__.
（2８） 假定一个图具有n个顶点与e条边，则采用邻接矩阵表示得空间复杂性为＿＿____O(ｎ２ )　＿_____， 采用邻接表表示得空间复杂性为______ O（ｎ+e） _____＿。
(２9) 对于长度为n得线性表，若进行顺序查找，则时间复杂度为_＿＿___ O(n）_＿__；若采用折半法查找，则时间复杂度为＿＿____ O（loｇ2n)__＿＿.
(30） 假设在有序线性表A［1、、2０]上进行折半查找,则比较一次查找成功得结点数为____1＿____＿＿，则比较二次查找成功得结点数为___＿２_＿＿____，则比较三次查找成功得结点数为＿_＿_4_＿_____，则比较四次查找成功得结点数为＿_＿__8＿_＿_＿＿，则比较五次查找成功得结点数为_＿__5____＿_＿，平均查找长度为___＿＿　lｏg2(n+１)-1_＿＿＿_＿.
（3１） 在一棵二叉排序树中，每个分支结点得左子树上所有结点得值一定__＿＿＿小于__＿___该结点得值,右子树上所有结点得值一定____大于_＿＿____该结点得值。
（3２) 对一棵二叉排序树进行中序遍历时,得到得结点序列就是一个____＿__增序序列_＿＿_______＿____。
（33）　对于线性表(７0，34，55，23，６5,41,２0）进行散列存储时，若选用Ｈ(Ｋ)=K ％7作为散列函数,则散列地址为０得元素就是＿＿___70__＿_＿____,散列地址为6得就是_＿＿_３4，20，55＿_＿______。
(34） 在线性表得散列存储中，装填因子a又称为装填系数，若用ｍ表示散列表得长度，n表示待散列存储得元素得个数,则ａ等于＿_＿_ ｎ/m ____＿__。
（35） 散列表中解决冲突得两种方法就是____开放地址法__＿__＿＿__与____链地址法__＿______.
（36） 在散列存储中,装填因子ａ得值越大，则_＿__＿__产生冲突得可能性就越大___＿＿＿___＿__;a得值越小，则__＿__产生冲突得可能性就越小___＿___＿_＿_.
(３７）　散列法存储得基本思想就是由＿___＿___关键码直接____＿_________决定数据得存储地址.
（３8) 构造哈希函数得方法有（写二个)___＿＿___＿_____直接定址法,数字分析法，平方取中法,折叠法，除留余数法,随机数法____＿_＿＿＿_＿＿＿____＿_＿＿＿___＿＿_____＿______＿_。
(39） 在分块查找中首先查找 ___＿_索引________,然后再查找相应得______块＿________。
(40) 散列表得查找效率主要取决于散列表造表时选择得_＿___哈希函数______＿＿ 与_____＿装填因子__＿___＿__。
（41）　 对两棵具有相同关键字集合而形状不同得二叉排序树,_＿＿_中序_＿__＿＿_ 遍历它们得到得序列得顺序就是一样得。
（42) 当待排序得记录数较大,排序码较随机且对稳定性不作要求时，宜采用_____＿快速__＿__＿＿__排序;当待排序得记录数较大，存储空间允许且要求排序就是稳定时，宜采用＿__＿__归并________＿排序.
(43）　 在堆排序得过程中，对任一分支结点进行筛运算得时间复杂度为___ O（log2n）__＿__,整个堆排序过程得时间复杂度为____ Ｏ(nloｇ２n）＿___。
（４４) 当向一个大根堆插入一个具有最大值得元素时,需要逐层__＿_向上＿＿＿＿＿调整，直到被调整到__＿＿_根结点______＿位置为止.
(４5)　　对一组初始关键字序列(４0，５0,９5，2０，1５，70,60,45，10）进行冒泡排序,则第一趟需要进行相邻记录得比较得次数为_＿__8＿_＿＿_＿，在整个排序过程中最多需要进行_＿___8___＿_趟排序才可以完成.
(4６) 　在在插入排序、选择排序、快速排序、堆排序、归并排序与基数排序中,平均比较次数最少得排序就是__＿快速＿_＿____,需要内存容量最多得就是＿＿__归并_＿＿_＿_。
（47) 堆排序就是不稳定,空间复杂度为 _＿_＿ O（1)__＿__。在最坏情况下，其时间复杂度也为_＿_　O(nｌｏg２n）__＿___。
(４8）　 若待排序得文件中存在多个关键字相同得记录，经过某种排序方法排序后，具有相同关键字得记录间得相对位置保持不变，则这种排序方法就是____稳定_______得排序方法.
(49) 在对一组记录（50，４0，95，２0,１5，70,6０,4５，80）进行直接插入排序时，当把第７个记录６０插入到有序表时,为寻找插入位置需比较__＿＿３＿____次。
（５0) 二路归并排序得时间复杂度就是＿__ Ｏ(nｌog2n）_＿____.
（51) 对于ｎ个记录得集合进行归并排序,所需得附加空间消耗就是__＿ Ｏ（n)_＿____.
（52） 设表中元素得初始状态就是按键值递增得，分别用堆排序、快速排序、冒泡排序与归并排序方法对其仍按递增顺序进行排序,则______冒泡排序____＿____最省时间，＿＿＿_快速排序__＿＿_＿__最费时间。
三、判断题。(每小题1分,共10分）
（　× )1．数据元素就是数据得最小单位。
（ × ）2。数据项就是数据得基本单位。
（ √ ）3。顺序存储得线性表可以随机存取。
(　√　)4．线性表中得元素可以就是各种各样得，但同一线性表中得数据元素具有相同得特性, 因此,就是属于同一数据对象。
（ × ）5.在单链表中，任何两个元素得存储位置之间都有固定得联系，因为可以从头结点查找任何一个元素。
( ×　）６．在单链表中，要取得某个元素,只要知道该元素得指针即可,因此,单链表就是随机存取得存储结构。
( × )7.链表得每个结点中，都恰好包含一个指针。
（ × )8。数组就是同类型值得集合. 　 　　 　
（ √ ）9。使用三元组表示稀疏矩阵得元素,有时并不能节省存储时间。
（ √　）10、 线性表可以瞧成就是广义表得特例,如果广义表中得每个元素都就是原子，则广义表便成为线性表。
（ √ )１1、 由树转换成二叉树，其根结点得右子树总就是空得。
(　× ）12、 后序遍历树与中序遍历与该树对应得二叉树,其结果不同。
( × )13、 若有一个结点就是某二叉树子树得中序遍历序列中得最后一个结点,则它必就是该子 树得前序遍历序列中得最后一个结点.
（ √ ）1４、若一个树叶就是某子树得中序遍历序列中得最后一个结点，则它必就是该子树得前序　遍历序列中得最后一个结点。
( × ）15、 已知二叉树得前序遍历与后序遍历序列并不能唯一地确定这棵树，因为不知道树　得根结点就是哪一个。
（ × )16、 在哈夫曼编码中，当两个字符出现得频率相同时，其编码也相同,对于这种情况应作特殊处理。
（ √ ）1７、 有回路得图不能进行拓扑排序。
(　× )18、 连通分量就是无向图中得极小连通子图。
( √ ）19、　散列法存储得基本思想就是由关键码得值决定数据得存储地址.
( √　）20、 散列表得查找效率取决于散列表造表时选取得散列函数与处理冲突得方法.
（ √　）21、　m阶B-树每一个结点得子树个数都小于或等于ｍ。
( √ ）２2、 中序遍历二叉排序树得结点就可以得到排好序得结点序列。
（ √ )23、 在二叉排序树上插入新得结点时，不必移动其它结点,仅需改动某个结点得指针， 由空变为非空即可。
（ √　)２4、　当待排序得元素很多时,为了交换元素得位置，移动元素要占用较多得时间，这就是影响时间复杂性得主要因素。
( √ ）25、 对于n个记录得集合进行快速排序，所需要得平均时间就是O(nｌoｇ2 n）。
( √　）26、　对于n个记录得集合进行归并排序，所需要得平均时间就是Ｏ(nloｇ2　ｎ)。
( √ )27、 堆中所有非终端结点得值均小于或等于（大于或等于）左右子树得值。
( × ）２8、 磁盘上得顺序文件中插入新得记录时，必须复制整个文件。
（ ×　)29、　在索引顺序文件中插入新得记录时，必须复制整个文件.
( ×　)30、 索引顺序文件就是一种特殊得顺序文件，因此通常存放在磁带上。
四、简答题。(共6小题,每小题约5分,共32分)
1、 简述下列术语：数据、数据项、数据元素、数据逻辑结构、数据存储结构、数据类型与算法。
数据：数据就是信息得载体,就是计算机程序加工与处理得对象,包括数值数据与非数值数据。
数据项：数据项指不可分割得、具有独立意义得最小数据单位，数据项有时也称为字段或域。
数据元素:数据元素就是数据得基本单位，在计算机程序中通常作为一个整体进行考虑与处理,一个数据元素可由若干个数据项组成.
数据逻辑结构：数据得逻辑结构就就是指数据元素间得关系。
数据存储结构：数据得物理结构表示数据元素得存储方式或者数据元素得物理关系.
数据类型：就是指变量得取值范围与所能够进行得操作得总与.
算法：就是对特定问题求解步骤得一种描述,就是指令得有限序列。
2、 简述栈与线性表得区别.
答：一般线性表使用数组来表示得。线性表一般有插入、删除、读取等对于任意元素得操作。
而栈只就是一种特殊得线性表.栈只能在线性表得一端插入（称为入栈，push)或者读取栈顶元素或者称为“弹出、出栈”（poｐ）。
3、 简述栈与队列这两种数据结构得相同点与不同点。
答：相同点：栈与队列都就是特殊得线性表，只在端点处进行插入,删除操作.
不同点:栈只在一端（栈顶）