数据结构习题.

1、数据结构习题1. 算法的计算量的大小称为计算的B。A.效率 B.复杂性 C.现实性 D.难度2. 算法的时间复杂度取决于 CA.问题的规模B.待处理数据的初态C. A和B3. 计算机算法指的是C,它必须具备B这三个特性。(1) A.计算方法B.排序方法C.解决问题的步骤序列D.调度方法(2) A 可执行性、可移植性、可扩充性B. 可执行性、确定性、有穷性C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性4. 一个算法应该是 CA.程序B.问题求解步骤的描述C要满足五个基本特性D.A和C.5. 下面关于算法说法错误的是 DA. 算法最终必须由计算机程序实现B. 为解决某问题的算法同为该问

2、题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D.以上几个都是错误的6. 下面说法错误的是 B(1 )算法原地工作的含义是指不需要任何额外的辅助空间(2)在相同的规模n下，复杂度0(n)的算法在时间上总是优于复杂度0(2n)的算法( 3)所谓时间复杂度是指最坏情况下， 估算算法执行时间的一个上界( 4)同一个算法，实现语言的级别越高，执行效率就越低A(1)B.(1),(2) C.(1),(4) D.(3)7从逻辑上可以把数据结构分为 c 两大类A.动态结构、静态结构B.顺序结构、链式结构C.线性结构、非线性结构D.初等结构、构造型结构8以下与数据的存储结构无关的术语是 CA.循

3、环队列B.链表C.哈希表D.栈9以下数据结构中，哪一个是线性结构 ADA.广义表B.二叉树 C.稀疏矩阵D.串10以下那一个术语与数据的存储结构无关 BA.栈 B.哈希表 C.线索树D. 双向链表11.数据结构S中：元素的集合为：A，关系的集合为： , , , , , , , , ，贝U S 的逻辑结构为 D（A）集合（B）线性（C）树（D）图12. 数据元素之间存在一对多关系的数据结构是C（A）线性表（B）队列（C）二叉树（D）AOV-网13. 以下数据结构中,属于线性结构的有AA）线性表 （B）树 （C） 二叉树 （D） 图1数据的物理结构包括 数据元素 的表示和 关系 的表示。2. 对于

4、给定的 n 个元素 , 可以构造出的逻辑结构有 集合 , 线性结构 树状, 图 状四种。3数据的逻辑结构是 指数据元素之间的逻辑关系 。4. 数据结构是指 数据元素之间的逻辑关系 ,具体包含三个方面： 数据的逻辑结 构,数据的物理存储结构 和数据运算的集合 。5. 根据数据元素之间关系的不同特性,通常有 线性、 树形、图状和集合四类基 本逻辑结构,它们反映了四类基本的数据组织形式。6数据结构中评价算法的两个重要指标是 空间和时间的复杂度7.一个算法具有 5 个特性:有穷性、 确定性、可行性 ,有零个或多个输入、 有一个或多个输出。第一章1. 数据结构是指 【 指相互之间存在一种或多种特定关系的

5、数据元素集合； 】，具 体包含三个方面：数据的【 逻辑结构 】，数据的【 物理结构 】和 数据运算的集合 。2. 根据数据元素之间关系的不同特性， 通常有【集合结构】、【线性结构 】、【 树状结构 】、【 图状结构 】四类基本逻辑结构，它们反映了四类基本的数据组织形 式。3. 数据结构S中：元素的集合为：A ,B ,C,D, E, F ,G,H , I,关系的集合为： , , , , , , , , ，贝U S 的逻辑结构为 （D）（A）集合 （B）线性 （C）树（D）图4. 数据元素之间存在一对多关系的数据结构是（ C ）（A）线性表（B）队列（C）二叉树（D）AOV-网5. 以下数据结构中

6、 属于线性结构的有（ A ）A）线性表 （B） 树 （C） 二叉树 （D） 图6. 存储结构是逻辑结构在计算机中的实现。 （ 对 ）7. 非空线性表中任意一个数据元素都有且仅有一个直接前驱元素。 （ 错 ）8. 非空线性表中任意一个数据元素都有且仅有一个直接后继元素。 （ 错 ）9. 顺序存储结构只能用来存放线性结构；链式存储结构只能存放非线性结 构。 （ 错 ）10. 算法就是程序。 （ 错 ）11.种逻辑结构可以采用不同的存储方式存放在计算机中第二章1. 线性结构的基本特征是 : 若至少含有一个结点，则除起始结点没有直接 【 前驱 】外，其他结点有且仅有一个直接【 前驱 】 ; 除终端结点

7、没有直 接【 后继 】外，其它结点有且仅有一个直接【 后继 】。2. 线性表的顺序存储结构是指用一组【 地址连续 】的存储单元依次存储 线性表中的各个元素，逻辑上相邻的元素，其物理位置【 连续 】_。链 式存储结构中，逻辑上相邻的元素，其物理位置【不一定连续 】 。3. 线性表的顺序存储结构中，逻辑上相邻的元素，其物理位置【 连续 】。 链式存储结构中，逻辑上相邻的元素，其物理位置【 不一定连续 】 。4. 在顺序表中插入或删除一个元素，需要平均移动【表长一半 】元素，具体移动的元素个数与【 插入或删除的位置 】有关。5. 单链表是线性表的的【 链式 】存储结构。6. 单链表表示法的基本思想是

8、用【 指针域 】表示结点间的逻辑关系。7. 循环链表与单链表的区别仅仅在于循环链表尾结点的链域值不是 【 NULL 】，而是一个指向【 表头指针 】的指针。8. 如右图所示，在单键表中，P指针所指结点之后插入一个新结点 S，操作 的语句是： 【 s-next=p-.next 】； 【 p-next=s 】。9. 顺序表的类型中，假定每个 datatype 类型的变量占用 k（k=1） 个内存单 元，其中， b 是顺序表的第一个存储结点的第一个单元的内存地址， 那么， 第i个（K i菊n吉点ai的存储地址为【b+（i-1）*k】。10. 在单链表中，删除P指针所指向的结点的后继（S指针指向的结点

9、）的操作是 【 p-next=s-next】 ；free（ 【 s 】 ）。11. 以下为顺序表的插入运算，分析算法，请在空白处填上正确的语句。void insert_seqlist(seqlist *L， datatype x ，int i)/* 将 x 插入到顺序表 L 的位序为 i 的位置 */ if( L-last = maxsize- 1 ) error( 表“满”；) if(iL-last+2) error(“非法位置 ”);for(j=L-last;j=i-1;j-)【 L-dataj+1=L-dataj 】;L-datai-1=x;【 L-last+ 】 ;12. 以下为顺序表

10、的删除运算，分析算法，请在空白处填上正确的语句void delete_sqlist(sqlist *L,int i)/*删除顺序表L中的第i-1个位置上 的结点 */if(iL-last)error( “非法位置” ) ；for(j=i+1;j=L-last;j+)【 L-dataj-1=L-dataj】 ;L-last=L-last-1;13. 下列有关线性表的叙述中，正确的是( D )。(B) 线性表中任何一个(D) 以上说法都不正确(A) 一个线性表是 n 个数据元素的有限序列 元素有且仅有一个直接前驱(C) 线性表中任何一个元素有且仅有一个直接后继14. 顺序表是线性表的( B )。(

11、A) 链式存储结构 (B) 顺序存储结构 (C) 索引存储结构 (D) 散列存储结构15.从一个长度为n的顺序表中删除第i个元素(1 i胡时)需向前移动( A) 个元素。(A) n-i(B)n-i+1(C)n-i-1 (D)i16. 一个长度为n的顺序表中第i个位置上插入新元素(1 i next = = NULL (C) head-next= = head (D) head != NULL23. 在带头结点的非空单链表H中，指针p指向某的结点，求p结点的前驱 结点指针 q 的算法是( B )。(A) q=H ; while(q!=p) q=q-next;(B) q=H ;while(q-nex

12、t!=p) q=q-next;(C) q=H-next ; while(q!=p) q=q-next;(D) q=H-next ;while(q-next!=p) q=q-next;24. 在带头结点的单链表H中，求单链表长度len的算法是(A )。(A) len=0,p=H ; while(p-next!=NULL) len + ; p=p-next;(B) len=0,p=H-next ; while(p-next!=NULL) len + ; p=p-next;(C) len=1,p=H ; while(p!=NULL) p=p-next; len + ; (D) len=1,p=H-n

13、ext ; while(p-next!=NULL) p=p-next; len + ;25. 假设指针p指向单链表中的某一结点,s为某结点指针，则在p指针后面插 入结点 s 的操作是( C )。(A) p-next=s;s=p-next; (B)p-next=s;s-next=p-next;(C) s-next=p-next;p-next=s; (D)s-next=p;p-next=s;26. 假设指针p指向单链表中的某一结点,s为某结点指针，则在p指针前面插 入结点 s 的操作是( 无正确答案 )。(A) s-next=p-next;p-next=s; (B)p-next=s; s-next

14、=p-next;(C) p-next=s ; s=p-next;(D) s-next=p ; p-next=s;27. 在单链表中，指针p指向元素为X的结点，实现 删除X的后继”勺语句是 （ B ）。（A）p=p- next;（B）p- next =p- next - next ;（C）p- next=p;（D）p=p- next- next;28. 某线性表中最常用的操作是存取序号为i 的元素及其前驱的值， 可采用的存储的方式是（ A）。（A）顺序表（B）单向链表（C）双向循环链表（D） 单向循环链表29. 对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为 （ C ）。（A）顺

15、序表（B）用头指针表示的单循环链表（C）用尾指针表示的单循环链表（D）单链表30. 在单链表中，头结点是必不可少的。 （ 错 ）31. 在单链表中，头结点的作用是简化运算。 （ 对 ）32. 在线性表的顺序存储结构中， 逻辑上相邻的数据元素在物理位置上也是相邻的。 （对 ）33. 在线性表的链式存储结构中， 逻辑上相邻的数据元素在物理位置上也是相邻的。 （错 ）34. 只要内存足够大，采用链式存储结构的线性表长度不受限制。 （ 对 ）第三章1. 仅允许在表的一端进行插入与删除操作的线性表称作【 栈 】，允许在 表的一端进行插入，另一端进行删除操作的线性表 称作【 队列 】。2. 栈称为【 后进

16、先出 】线性表。队称为【 先进先出 】线性表。3. 队列的操作是按【 先进先出 】的原则进行的。4. 栈的运算特点是【 后进先出 】。请将用 C 语言的顺序栈的定义补充完typedef struct 【 ElementType dataMaxsize 】；【 int top 】； seqstack ；5. 以下运算实现在顺序栈上的进栈，请在空白处用适当的语句予以填充。typedef structDataType datamaxsize ；int top ；SeqStack；int Push(SeqStack *sq ,DataType x) if(sp-top= maxsize-1) erro

17、r( “栈满”)；return(O) ； else 【 sp-top+ 】；【 sp-datasp-top 】=x；return(1) ；6. 队列的操作是按【 先进先出 】原则进行的。循环队列 Q 分配 Maxsize 个存储单元，队头指针为front,队尾指针为rear，采用少用一个空间的 方法处理，判断队列满的条件是【 front=(rear +1)%Maxsize 】。7. 循环队列是队列的【 顺序 】存储结构。8. 循环队列Q分配Maxsize个存储单元，队头指针为front,队尾指针为rear， 采用少用一个空间的方法处理,判断队列满的条件是【 front=(rear +1)%Ma

18、xsize 】。9. 以下顺序栈定义及出栈运算实现,请在空白处用适当语句填充。typedef structDataType datamaxsize ；int top；SeqStack；int Pop(SeqStack *sp ，DataType *x) if (sp-top=0) error( 空“栈 ” )； return(0) ； else *x=_ sp-datasp-top_ ；_sp-top-_ ；return(1) ； 10. 栈操作的原则是( B )。(A) 先进先出(B)后进先出(C)栈顶插入(D) 栈顶删除11. 栈的两种常用存储结构分别为 A(A) 顺序存储结构和链式存储结

19、构 (B) 顺序存储结构和散列存储结构(C) 链式存储结构和索引存储结构 (D) 链式存储结构和散列存储结构12. 有一栈，元素 A，B，C，D 依次进栈 ,则以下出栈序列中不可能得到的是 ( D )。(A)D、C、B、A(B) C、B 、A、D (C) A 、B、C 、D (D) D 、C、A、B13. 一个栈的入栈序列是 A,B,C,D,E, 则不可能的出栈序列是( C)。(A)EDCBA C)DCEAB(B)DECBA(D)ABCDE14. 若进栈序列为a, b, c,贝U通过入出栈操作可能得到的a, b, c的不同排 列个数为 B(A)4(B)5(C)6(D)715. 循环队列是队列的

20、( A )。(A)顺序存储结构(B)链式存储结构(C)索引存储结构(D)散列存储结构16. 设循环队列中数组的下标范围是1n,其头尾指针分别是f、r，则队列 中元素个数为( D )。(A)r - f (B)r f + 1(C)(r -f + 1)mod n (D)( r -f+ n ) mod n17. 在循环队列中 ( 少用一个存储空间 ),队满的条件是(A)。(A)(rear+1)%maxsize=front(B) raer=front(C) (front+1)%maxsize=rear(D)rear=018. 循环队列的队满条件为( C )。(A) (sq.rear+1) % mazsi

21、ze =(sq.front+1) % maxsize;(B) (sq.rear+1) % maxsize =sq.front+1(C) sq.(rear+1) % maxsize =sq.front(D) sq.rear =sq.front19. 设数组 datam 作为循环队列 SQ 的存储空间， front 为头指针， rear 为尾 指针，执行出队操作 ,其头指针的值为( D )。(A) front=front+1 (B) front=(front+1)%(m-1) (C) front=(front-1)%m (D) front=(front+1)%m20. 栈和队列与线性表的逻辑结构相

22、同。 ( 对 )21. 栈只能在栈顶进行插入和删除。 (对 )22. 队列只能在队首进行删除，在队尾进行插入。 ( 对 )23. 队列只能在队尾进行删除，在队首进行插入。 ( 错 )第四章1. 通常采用【顺序 】存储结构来存放数组 。对二维数组可有两种存储方 法：一种是以【 行 】为主序的存储方式，另一种是以【 列 】为主序的 存储方式。2. 已知具有 n 个元素的一维数组采用顺序存储结构， 每个元素占 k 个存储单 元，第一个元素的地址为L0C(a1)，那么，LOC(ai)=【Ioc(a1)+(i+1)*k】3.在C语言中定义的二维数组int M1020，每个元素(整数)占两个存储 单元，数

23、组的起始地址为 2000，M819 的存储值为【 2358 】。元素M510 的存储位置为【 2220 】。4假设有6行8列的二维数组A，每个元素占用6个字节，存储器按字节编 址。已知 A 的基地址为 1000，那么元素 A3， 6在按行存储时的地址是 【 1126 】，按列存储时的地址是【 1192 】。5. 对称方阵采用压缩存储， 即为每一对对称位置元素只分配一个存储空间，则可将n2个元素压缩存储到【n*(n+1)/2】个元素的存储空间中。6. 有一个 10 阶对称矩阵 A1010 ，采用压缩存储方式以行序为主存储， A00的位置是1，则A85的位置是【42】。7. 三元组表是【 稀疏矩阵

24、 】的【 顺序 】存储结构。8. 字符串S= Computer”中，以p为首字符的子串有【5】个。9. TAILHEAD(a,b),(c,d) 运算的结果是【 (b) 】。10. 广义表 L=( x,a) ,(x,a,(b,c),y )的长度是【 3 】。11. 设广义表 A=(a,b),B=(c,d), 求 head( (A, B) ) 的值为【 (a,b)】。12. 有如下稀疏矩阵，请写出它的三元组表： m=6 n=6 t=913. 串是( D )。(A) 一些符号构成的序列 (B) 有限个字母构成的序列(C) 一个以上的字符构成的序列 (D) 有限个字符构成的序列14.已知函数Sub(s

25、,i,j)的功能是返回串s中从第i个字符起长度为j的子串， 函数Scopy(s,t)的功能为复制串t到s。若字符串S= “SCIENCESTUDY， 则调用函数Scopy(P,Sub(S,1,7)后得到(A )。(A)P= “SCIENCE” (B)P= “STUD”Y (C)S= “SCIENCE” (D)S= “STUD”Y15. 设有一个二维数组A68,假设A00存放位置在1000,每个元素占6 个空间，按行优先存储，则 A36 的存储位置是 _B_(A)1180(B)1126(C)126(D)18016. 一个向量第一个元素的存储地址是 100，每个元素的长度为 2，则第五个元素的地址

26、是 _B 。(A)110(B)108(C)100(D)12017. 为了节省存储空间，将n阶对称矩阵A(下标从1开始)中包括主对角线元 素在内的下三角部分的所有元素按照行序为主序方式存放在一维数组B1:n(n+1)/2中，对任意下三角部分的元素 aij(i在数组B的下标k是 B 。(A)i(i-1)/2+j-1(B)i(i-1)/2+j(C)i(i+1)/2+j-1(D)i(i+1)/2+j18. 基于三元组的稀疏矩阵，对每个非零元素 aij, 可以用一个( _B_ )唯 一确定。(A) 非零元素(B)三元组(i,j,aij)(C) aij(D) i,j的长度为 _ _B_ (C)4(D)51

27、9. 广义表 A=(),(a),(b,(c,(D)(A)2(B)320. 空串与由空格组成的串没有区别。 ( 错 )21. 对称矩阵的压缩存储是指对矩阵中的值相同的元素只分配一个存储空间 (对 )22. 对称矩阵的压缩存储是指对矩阵中的规律元素只分配一个存储空间。( 对)23. N阶下三角矩阵压缩存储需要n*(n+1)/2个存储空间。(对 )24. 三元组表是稀疏矩阵的顺序存储结构。 ( 对 )第六章I. 在二叉树中，第i层的结点数最多为【2A (i-1 )】；2深度为k的二叉树的结点总数最多为【2Ak-1】。3. 对任何二叉树，若度为2的节点数为n2,贝U叶子数nO=【n2+1】。4. 在一

28、棵完全二叉树中， 若编号为 i 的结点有左孩子， 则该左孩子结点的编 号为【 2i 】；若编号为 i 的结点有右孩子，贝该右孩子结点的编号为【 2i+1】。5. 一棵深度为 5 的二叉树最多有【 31】 个结点。6. 深度为 h 且有【 2Ah-1 】个结点的二叉树称为满二叉树。 ( 设根结点处 在第 1 层)。7. 具有 n 个结点的完全二叉树， 若按层次从上到下、 从左到右对其编号 (根结点为 1 号)，贝编号最大的分支结点序号是【 n/2 】，编号最小的分 支结点序号是【1】，编号最大的叶子结点序号是【n】，编号最小的叶子结点序号是【 n/2+1】。8. 在有 n 个结点的二叉树， 采用

29、二叉链表存放， 空链域的个数为 【 n+1】。9. 二叉树通常有【 顺序 】存储结构和【 二叉链表 】存储结构两类存储 结构。10. 给定二叉树的两种遍历序列，分别是：前序遍历序列：D， A， C， E， B，H，F，G，I;中序遍历序列：D，C，B，E，H，A，G，I，F,试画出二叉树。 题出错II. 请对给定的二叉树的存储结构， 将二叉树的中序遍历输出结点递归算法补 充完整：typedef struct node char data；/* 元素为字符型 */struct node * Lchild ， *Rchild ； *BiTree ；void Inorder(BiTree root

30、) if ( root != NULL )【 Inorder(root-Lchild) 】；【 Visit ( root-data ) 】；【 inorder ( root-Rchild )】；12. 请对给定的二叉树的存储结构， 将二叉树的先序遍历输出结点递归算法补 充完整：typedef struct node char data; /* 元素为字符型 */struct node * Lchild,*Rchild; BiTree;void preorder(BiTree root ) if ( root != NULL ) 【Visit ( root-data ) 】;【 preorder

31、 (root-Lchild ) 】 ;【 preorder ( root-Rchild ) 】;13. 以下程序段采用先根遍历方法求二叉树的叶子数， 请在横线处填充适当的 语句。void countleaf(bitree *t,int *count)/*根指针为 t,假定叶子数 count 的初值为 0*/if(t!=NULL) if(t-lchild=NULL)&(t-rchild=NULL)【 count=0】;countleaf(t-lchild,&count);【 countleaf(t-rchild,&count)】14. 哈夫曼树是带权路径长度 【 最短 】的树,通常权值较大的结点

32、离根 【较 近 】。15. 有m个叶子结点的哈夫曼树，其结点总数为【2m-1】。16. 用5个权值3, 2, 4, 5, 1构造的哈夫曼树的带权路径长度是 33 。选择题：17. 按照二叉树的定义，具有 3 个结点的二叉树有 _C种形态。(A)3 (B)4 (C)5 (D)618. 二叉树是非线性数据结构，它( C )。(A) 不能用顺序存储结构存储 ;(B) 不能用链式存储结构存储 ;(C) 顺序存储结构和链式存储结构都能存储 ;(D) 顺序存储结构和链式存储结构都不能使用19. 下列陈述中正确的是( D )。(A) 二叉树是度为 2 的树(B) 二叉树中结点只有一个孩子时无左右之分(C)

33、二叉树中必有度为 2 的结点(D) 二叉树中最多只有两棵子树，并且有左右之分20. 设有一棵 22个结点的完全二叉树，那么整棵二叉树有( D )个度为 0 的结点 ?(A)6(B)7(C)8(D)1121. 某非空二叉树共有叶结点 15 个，没有度为 1的结点，则该树共有( A ) 个结点。(A)29(B)28(C)27(D) 不能确定22. 已知完全二叉树有 26个结点，则整棵二叉树有( A )个度为 1 的结 点？(A)1(B)0(C)2(D)不确定23. 将一棵有 50个结点的完全二叉树编号，根结点为 1，每层从左到右依次 编号，则编号为 49 的结点的双亲结点的编号是( B )。(A)

34、23(B) 24(C) 25(D)2624. 对二叉树从 1 开始编号，要求每个结点的编号大于其左右孩子的编号， 同 一个结点的左右孩子中， 其左孩子的编号小于其右孩子的编号， 则可采用 ( C )方法实现编号。(A) 前序遍历 (B) 中序遍历 (C) 后序遍历 (D) 从根开始进行层次遍历25. 一棵二叉树有 n 个结点，要按某顺序对该二叉树中的结点编号， (号码为1-n)，编号须具有如下性质：二叉树中任一结点 V，其编号等于其左子 树中结点的最大编号加 1。而其右子树中结点的最小编号等于 V 的编号加 1 。试问应按( B )遍历顺序编号。(A)前根 B中根 C后根 D层次27. 某二叉

35、树的中序遍历为：BDAEC后序遍历为：DBECA则前序遍历为(A )。(A)ABDCE(B)ADBCE(C)ABDEC(D)BDACE28. 已知二叉树的先序序列为ABDECJF中序序列为DBEAFC则后序序列为( D )。(A)DEBAFC (B)DEFBCA (C)DEBCFA (D)DEBFCA29. 在有 n 个叶子结点的哈夫曼树中，其结点总数为( D )。(A) 不确定 (B)2n(C)2n+1(D) 2n-130. 哈夫曼树的带权路径长度是( B )。(A) 所有结点权值之和 (B) 所有叶结点带权路径长度之和(C) 权结点的值(D) 除根以外所有结点权值之和31. 下列说法正确的

36、是( A )。(A) 树的先根遍历序列与其对应的二叉树的先根遍历序列相同(B) 树的先根遍历序列与其对应的二叉树的后根遍历序列相同(C) 树的后根遍历序列与其对应的二叉树的先根遍历序列相同(D) 树的后根遍历序列与其对应的二叉树的后根遍历序列相同 判断题：32. 对于一棵任意二叉树，若叶子结点数为 nO,度为2的结点个数为n2，则 有 n2= n0+1 。 ( 错 )33. 对于一棵任意二叉树，若叶子结点数为 nO,度为2的结点个数为n2，则 有 nO= n2+1 。 ( 对 )34. 深度为 n 的非空二叉树的第 i 层最多有 2n-1 个结点。 ( 错 )35. 非空二叉树的第 i 层最多

37、有 2i-1 个结点。 （ 对 ）36. 二叉树中，任何一个结点的度为 2。（ 错 ）37. 二叉树中每个结点的两棵子树是有序的。 （ 对 ）38. 具有 12 个结点的完全二叉树有 4 层深。（ 对 ）39. 具有 12 个结点的完全二叉树有 5 个度为 2 的结点。 （ 对 ）40. 线索二叉树是在二叉树的所有结点的存储结构中增加先驱和后继指针得 到的。 （ 错 ）41. 已知一棵二叉树的前序序列和中序序列可以唯一地构造出该二叉树。（ 对）42. 已知一棵二叉树的前序序列和后序序列可以唯一地构造出该二叉树。（ 错）43. 哈夫曼树中不存在度为 1 的分支结点。 （ 对 ）44. 有 n 个

38、叶子结点的哈夫曼树共有 2n-1 个结点。 （ 对 ）第七章1. 在无向图中，如果从顶点V到顶点V有路径，则称V和V是【连通 】的。2. 图的存储结构主要有【 顺序存储 】和【 链式存储 】两种。3. 遍历图的基本方法有【 深度 】优先搜索和【 广度 】优先搜索两种。4. 有如图所示的图的邻接矩阵， 从 1 顶点出发对该图进行深度优先搜索的结 点序列是【 1,2,3,4,6,5 】，广度优先搜索的结点序列是 【 1,2,3,5,6,4 】。5. 若连通图G的顶点个数为n,则G的生成树的边数为【n-1】。6. 有向图G用邻接矩阵存储，其第i行的所有元素之和等于顶点i的【出】 度。7. 有向图G用

39、邻接矩阵存储，其第i列的所有元素之和等于顶点i的【入】 度。8. 无向图的邻接矩阵是一个【 对称 】矩阵；在邻接矩阵上，无向图中顶点 Vi 的度为【 2 】； 邻接表上，无向图中顶点 Vi 的度为【 1 】。9. 一个具有 n 个顶点的简单无向图最多（ C ）条边。(A)n(B)n(n-1)(C)n(n-1)/2(D)2n10. 有 8个结点的无向连通图最少有( C )条边。(A)5 (B) 6 (C)7 (D)811. 一个具有 n 个顶点的无向完全图的边数为 B(A) n(n+1)/2 (B) n(n-1)/2 (C) n(n-1) (D) n(n+1)12. 任何一个带权的无向连通图的最

40、小生成树 B(A)只有一棵(B)有一棵或多棵(C) 一定有多棵(D)可能不存在13. 已知一个有向图2,则从顶点a出发进行深度优先遍历，不可能得到的 DFS 序列为 D(A) a d b e f c B .a d c e f bC .a d c b f e(D) a d e f c b14. 对下图 1 所示的带权有向图，从顶点 1 到 5 的最短路径为( D )。(A)1,4,5(B)1,2,3,5(C)1,4,3,5(D)1,2,4,3,516. 某有向图由m个顶点和n条边组成，使用邻接表进行存储，则该邻接表由 m 个头结点和 n 个表结点组成。 ( 错 )17. 用邻接矩阵存储一个图时，

41、 在不考虑压缩存储的情况下， 所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。(对 )18. 有 n 个结点的无向完全图有 n*(n-1)/2 条边。( 对 )19. 有 n 个结点的有向完全图有 n*(n-1)/2 条边。( 错 )20. 某无向图由m个顶点和n条边组成，使用邻接表进行存储，则该邻接表由 m 个头结点和 n 个表结点组成。 ( 错 )21. 有向图中所有顶点的入度之和等于所有顶点的出度之和。 ( 错 )22. 普里姆算法是采用“加边法”构造最小生成树的。 ( 错 )23. AOE网是一种带权的无环连通图。(错)24. AOE网是一种带权的有向无环图。(对)25.

42、AOE网所表示的工程至少所需要的时间等于从源点到汇点的最长路径长 度。 （ 对 ）26. AOE网来表示工程计划时，从源点到汇点的最短路径表示了关键路径。 （ 错）27. AOV网的拓扑序列是唯一的。（错）28. 带权连通图的最小生成树的权值之和是它的生成树的权值之和中最小的。 （ 对 ）29. 带权连通图的最小生成树的权值之和一定小于它的其它生成树的权值之 和。 （ 对 ）30. 迪杰斯特拉（Djkstra ）算法是按照最短路径长度递增的顺序产生所有的 最短路径。 （ 错 ）第 八、九章1. 折半查找对待查找的列表有两个要求：（ 1）采用【.顺序】存储结构（ 2）关键字【 有序】排列。2.

43、在线性表中采用折半查找法查找一个数据元素， 线性表中元素应该按值有 序，并且采用【 . 顺序 】存储结构。3. 在表示一棵二叉排序树的二叉链表上，要找键值比某结点X的键值【小 】的结点，只需通过结点X的左指针到它的左子树中去找。4. 中根遍历一棵二叉排序树所得的结点访问序列是键值的 【升序 】序列。5. 在一棵空的二叉排序树中依次插入关键字序列为 12， 7， 17， 11， 16， 2， 13， 9， 21， 4，所得到的二叉排序树是【 】。6. 已知序列 （34， 76， 45， 18， 26， 54， 92， 65），按照逐点插入法建立一棵二叉排序列树，该树的深度是【 5】。7. 平衡因

44、子是【结点的左子树深度与右子数深度之差 】。平衡的二叉排序树的平衡因子的值只能是【 -1 0 1】。8. 哈希法中影响关键字比较次数的三个因素是： （1） 【哈希函数、 】（2）【处理冲突的方法 、】（ 3）【 哈希表的装填因子 】。哈希表的装填因子是：a =【哈希表中元素个数/哈希表的长度】。a的值越小，发生冲突的可能性越小，a的值越大，发生冲突的可能性越大。8. 在数值无规律的线性表中进行检索的方法是【 顺序查找 】9. 按照排序过程涉及的存储设备的不同，排序可分为【内】排序和【外】排序。10. 排序过程中一般进行两个基本操作（1）【 比较】（2）【移动 】。 其中（1）是必要的，（2）可

45、以采用适当的存储方式避免。11. 给定关键字（48, 62, 35, 77, 55, 14, 35, 98）进行一趟快速排序的结果是 【35 14 35 48 55 77 62 98】。12.若对序列（49 , 38, 65, 97, 76, 13, 27, 50）采用快速排序，则第一趟排序 后序列的状态是【 27 38 13 4976 97 65 50】。12. 设有散列函数H（k）=k mod 13散列表为T012，用线性探测再散列。 假定在某一时刻T的状态为：T0123456789110 1 280853415、下一个被插入的关键码是 42,其插入的位置是：【4】。16. 请将直接选择排

46、序算法补充完整：void SelectSort(RecordType R,int length)n = len gth;for(i=1;i=【n-1】;i+)k=【i】;for(j=i+1;j=n ;j+)if(Rj.key Rk.key )k=【j】if (【k!=i】)x=Ri;Ri=Rk;Rk=x;17. 以下简单选择排序算法，请将算法补充完整：void SelectSort(RecordType R , in t len gth)n=len gth;n-1 ; i+)for ( i=1 ;i=k=jfor ( j=i+1; j=n ; j+ )if( Rj.key R k.key )k

47、=j;if (k!=i)x=Ri ;Ri=Rk ;Rk=x;18. 以下是直接选择排序的算法。请分析算法，并在横线上填充适当的语句。void select(seqlist r,i nt n)for(i=1;i=【n-1】；i+)/*每次循环，选择出一个最小键值*/ k=i;for(j=i+1;j=n ;j+) if(rj.keyrk.key)【k=j 】;if( 【k!=i 】)swap(rk,ri);/* 函数 swap(rk,ri)交换rk和ri的位置*/19. 以下为直接插入排序的算法。请分析算法，并在 填充适当的语句。void straightsort(seqlist r,i nt n

48、)for(i=【2】；i=n;i+)r0=ri;j=i-1;while(rO.keyrj.key)rj+1=【rj】;j-;rj+1=【r0】;20. 直接插入排序的基本操作是：将第i个记录插入到前i-1个已排好序的记 录中。请将如下的直接插入排序算法补充完整：void InsSort ( RecordType R , int length)for(i=2 ; i=length ; i+)】; j-) R0= 【 rj for(j = i-1; 【 r0.keyrj.key Rj+1=Rj ;R 【 j+1 】 =R0;21. 请将如下的折半查找算法补充完整：int BinSrch ( SqL

49、ist L,KeyType k )low=1 ; high=L.length;/* 置区间初值 */ while( low=high)mid=【 (Low+High)/2 】;if (k= =L.rmid. key) return (mid); else if ( 【kL.rmid.key 】)high=mid-1;else 【 Low=mid+1】 ;return (0);22. 如下算法是折半查找算法，请将算法补充完整：typedef structKeyType key;OtherType other_data; RecordType;typedef struct RecordType r

50、Maxsize;int length;RecordList;int BinSrch (RecordListL,KeyType k)High= n-1;while ( low=high)mid = (Low + High)/2;if ( k= L.rmid.key) retur n (mid);else if( kL.rmid.key)high=mid-1else Low=mid+1;return (0);23. 如下算法是设置监视哨的顺序查找法，请将算法补充完整typedefstruct KeyTypekey;OtherTypeother_data;RecordType;typedef str

51、uctRecordType rMaxsize;in t le ngth;RecordList;int SeqSearch(RecordListL,KeyType k)L.data0.key =k;i=L .len gth;while(L. ri.key!= k )i-;return( i );24.单链表适用于（A ）查找(A) 顺序查找 (B) 折半查找 (C) 顺序查找，也能折半查找 (D) 随机25.对 12个记录的有序表作折半查找， 当查找失败时，最多需要比较(B )次关键字。(A) 3 (B)4 (C)5 (D) 626. 对线性表进行二分查找时，要求线性表必须(C )。(A) 以顺序方式存储 (B) 以链接方式存储(C) 以顺序方式存储， 且数据元素有序 (D) 以链接方式存储， 且数据方式有序27. 在关键字序列( 12，23，34，45，56，67，78，89，91)中二分查找关键字为 45，89和 12的结点时，所需进行的比较次数分别为( B )。(A) 4，4，3(B)4， 3，3(C)3，4，4(D)3，3，428. 设有序表的关键字序列为 1，4，6，10，18，35，