数据结构(c语言版)期末考试复习试题

1 习9解答

判断题：

1．用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。

答：FALSE (错。链表表示的有序表不能用折半查找法。)

2.有n个数据放在一维数组A[1..n]中，在进行顺序查找时，这n个数的排列有序或无序其平均查找长度不同。

答：FALSE (错。因顺序查找既适合于有序表也适合于无序表；对这两种表，若对于每个元素的查找概率相等，则顺序查找的ASL相同，并且都是(n+1)/2；对于查找概率不同的情况，则按查找概率由大到小排序的无序表其ASL要比有序表的ASL小。)

3.折半查找是先确定待查有序表记录的范围，然后逐步缩小范围，直到找到或找不到该记录为止。( )

答：TRUE

4.哈希表的查找效率主要取决于哈希表哈希表造表时选取的哈希函数和处理冲突的方法。

答：TRUE

5.查找表是由同一类型的数据元素(或记录)构成的集合。

答：TRUE

单选题：

6.对于18个元素的有序表采用二分(折半)查找，则查找A[3]的比较序列的下标为( )。

A. 1、2、3 B. 9、5、2、3 C. 9、5、3 D.9、4、2、3

答：D (第一次2/)181( = 9,第二次2/)81( = 4，第三次2/)31( = 2, (第四次2/)33( = 3，故选D.

7. 顺序查找法适合于存储结构为____________的线性表。

A.散列存储 B.顺序存储或链式存储

C.压缩存储 D.索引存储

答：B

8.对线性表进行二分查找时，要求线性表必须( )。

A．以顺序方式存储 B. 以链接方式存储

C．以顺序方式存储，且结点按关键字有序排序

D. 以链接方式存储，且结点按关键字有序排序

答：C

1 / 15 第一章 复习题

1.简述顺序存储结构与链式存储结构在表示数据元素之间关系上的主要区别。

答：在顺序结构中，逻辑关系上相邻的两个元素在物理位置上也相邻。而链式存储结构中，数据元素之间关系是由结点中指针指示的。

2.数据结构是一门……的学科。

3.在数据结构中，从逻辑上可以把数据结构分成〔 C 〕。

A、动态结构与静态结构

B、紧凑结构和非紧凑结构

C、线性结构和非线性结构

D、部结构和外部结构

4.编写一个函数，用不多于3n/2的平均比拟次数，在一个数组中找出最大和最小值元素。

void maxmin(int a[],int n)

{

max=min=a[0];

for(i=1;i

{

if(a[i]>max) max=a[i];

else if(a[i]

}

printf(“max=%d, min=%d〞,max, min);

}

第二章 复习题

1．下述哪一条是顺序存储结构的优点？〔 A 〕

A．存储密度大 B．插入运算方便

C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示

2．下面关于线性表的表达中，错误的选项是哪一个？〔 B 〕

A．线性表采用顺序存储，必须占用一片连续的存储单元。

B．线性表采用顺序存储，便于进展插入和删除操作。

C．线性表采用存储，不必占用一片连续的存储单元。

D．线性表采用存储，便于插入和删除操作。

3．线性表是具有n个〔 C 〕的有限序列〔n>=0〕 。

A．表元素 B．字符 C．数据元素 D．数据项

4．假设某线性表最常用的操作是存取任一指定序号的元素和在最后进展插入和删除运算，那么利用〔 A 〕存储方式最节省时间。

吉首大学题库

一、 一、 单选题（每题 2 分，共20分）

1. 1. 对一个算法的评价，不包括如下（ ）方面的内容。

A．健壮性和可读性 B．并行性 C．正确性 D．时空复杂度

2. 2. 在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行( )。

A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p;

C. p->next=HL; p=HL; D. HL=p; p->next=HL;

3. 3. 对线性表，在下列哪种情况下应当采用链表表示？( )

A.经常需要随机地存取元素 B.经常需要进行插入和删除操作

C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变

4. 4. 一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( )

A. 2 3 1 B. 3 2 1

C. 3 1 2 D. 1 2 3

5. 5. AOV网是一种（ ）。

A．有向图 B．无向图 C．无向无环图 D．有向无环图

6. 6. 采用开放定址法处理散列表的冲突时，其平均查找长度（ ）。

A．低于链接法处理冲突 B. 高于链接法处理冲突

C．与链接法处理冲突相同 D．高于二分查找

7. 7. 若需要利用形参直接访问实参时，应将形参变量说明为（ ）参数。

A．值 B．函数 C．指针 D．引用

1

习10解答

判断题：

1.排序的功能是将一个数据元素(或记录)的任意序列,重新排成一个按关键字有序的序列。( )

答：TRUE

2.直接插入排序的基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。( )

答：TRUE

3.使用简单选择排序方法无论记录的初始排列如何,所需进行的关键字间的比较次数相同。( )

答：TRUE

4.用希尔(Shell)方法排序时，若关键字的初始排序杂乱无序，则排序效率就低。（ ）

答：FALSE (希尔排序又称“缩小增量排序”，即每趟只对相同增量距离的关键字进行比较，这与关键字序列初始有序或无序无关)

单选题：

5.在对n个元素进行简单选择排序过程中，第i趟需从( )个元素中选择出最小值元素。

A．n-i+1 B. n-i C．i D. i+1

答：A

6. n个记录直接插入排序所需的记录最小比较次数是 ( )

A. n-1 B. 2(n-1) C. (n+2)(n-1)/2 D. n

答：A (注：如果初始记录序列就是一个符合要求的有序序列,则每趟操作只做一次比较，n-1趟操作仅需n-1次比较。参见严蔚敏《(c语言版)数据结构》P.265)

7. 若用起泡排序对关键字序列{18，16，14，12，10，8}进行从小到大的排序，所需进行的关键字比较总次数是（ ）

A．10 B. 15 C. 21 D. 34

答：B (注：参见严蔚敏《(c语言版)数据结构》P.274, 此题所给的初始序列为“逆序”，需要进行n(n-1)/2 = 6×(6-1)/2 = 15次比较。)

8. 用起泡法对n个关键码排序，在最好情况下，只需做 次比较；在最坏的情况下要做 次比较。