《数据结构》复习题

《数据结构》复习题

一、判断题

1、（ ）一个算法可以没有输入，但不能没有输出。 2、（ ）数据的物理结构是指数据在计算机内的实际存储形式。 3、（ ）链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结构中效率高。 4、（ ）栈和队列逻辑上都是线性表。 5、（ ）若输入序列为1,2,3,4,5,6,则通过一个栈可以输出序列3,2,5,6,4,1。 6、（ ）队列在数据中的存储原则是后进先出。 7、（ ）数组是同类型值的集合。 8、（ ）无向图的邻接矩阵是对称的，有向图的邻接矩阵是不对称的。 9、（ ）查找成功与否的关键在于是否按主关键字查找。 10、（ ）排序是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。 1、（ ）线性表的逻辑顺序与物理顺序总是一致的。 2、（ ）线性表的顺序存储表示优于链式存储表示。 3、（ ）深度为h的非空二叉树的第i层最多有2i-1 个结点。 4、（ ）栈和队列逻辑上都是线性表。 5、（ ）一般树和二叉树的结点数目都可以为0。 6、（ ）队列在数据中的存储原则是后进先出。 7、（ ）给定一组权值，可以唯一构造出一棵哈夫曼树。

二、选择题

1、在数据结构的讨论中把数据结构从逻辑上分为（ ）。 A 内部结构与外部结构 B 静态结构与动态结构 C 线性结构与非线性结构 D 紧凑结构与非紧凑结构 2、算法指的是（ ）。

A 计算机程序 B 解决问题的计算方法 C 排序算法 D 解决问题的有限运算序列 3、线性表采用链式存储时，结点的存储地址（ ）

A 必须是不连续的 B 连续与否均可 C 必须是连续的 D 和头结点的存储地址相连续

4、已知二维数组a[10][10]中，元素a[2][0]的地址为560，每个元素占4个字节，则元素a[1][0]的地址为（ ）。

A 520 B 522 C 524 D 518

5、树最适合用来表示( )。

A 有序数据元素 B 无序数据元素

C 元素之间具有分支层次关系的数据 D 元素之间无联系的数据

6、计算机识别、存储和加工处理的对象被统称为_________

A 数据 B 数据元素

C 数据结构 D 数据类型

7、设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。

A 5 B 6 C 7 D 8

8、二叉树中第5层上的结点个数最多为________

A 8 B 15 C 16 D 32

9、当采用分快查找时，数据的组织方式为 ( )

A．数据分成若干块，每块内数据有序

B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块

C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块

D. 数据分成若干块，每块（除最后一块外）中数据个数需相同

10、顺序查找方法的优点之一是( )

A 适合排序连续顺序文件的查找 B 对于被查找的对象几乎没有限制 C 适合链接顺序文件的查找

D 查找时间效率高

1、数据结构通常是研究数据的（ ）以及对数据的各种操作。 A存储和逻辑结构 B存储和抽象 C理想和抽象 D理想与逻辑

2、在堆栈中存取数据的原则是（ ） 。 A先进先出 B后进先出 C后进后出 D随意进出

3、将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子的编号为______。

A 98 B 99 C 50 D 48

4、图的深度优先遍历类似于二叉树的_______。

A 先序遍历 B 中序遍历 C 后序遍历 D 层次遍历

5、设单链表中结点的结构为

typedef struct node //链表结点定义

{

ElemType data； //数据

struct node * Link； //结点后继指针 } ListNode；

已知指针p所指结点不是尾结点，若在*p之后插入结点*s，则应执行下列哪一个操作______。

A s->link = p； p->link = s； B s->link = p->link； p->link = s； C s->link = p->link； p = s； D p->link = s； s->link = p；

三、填空题

1、数据结构课程研究的主要内容包括逻辑结构、________和算法三个方面。 2、线性表的常见链式存储结构有________、双向链表、循环链表。

3、若频繁地对线性表进行插入与删除操作，该线性表应采用____________存储结构。 4、通常像交通、道路问题的数学模型是一种称为________的数据结构。 5、在栈的顺序实现中，栈顶指针top，栈为空条件______________。

6、顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为________次。 7、设有一个行优先顺序存储的数组A[5][6]，A[0][0]的地址为1100，且每个元素占2个存储单元，则A[2][3]的地址为_____________。

8、度数为0的结点，即没有子树的结点叫作__________结点或_________结点。同一个结点的儿子结点之间互称为___________结点。

9、散列法存储的基本思想是由 决定数据的存储地址。

10、排序是指将无序的数据元素序列转变成一个有序序列，把序列中的记录，通过某些方法整理成__________递增或递减次序排列的处理过程。 1、《数据结构》课程讨论的主要内容是数据的逻辑结构、存储结构和______________。 2、一个算法应该具有______，确切性，可行性，输入和输出这五种特性。

3、若频繁地对线性表进行插入与删除操作，该线性表应采用____________存储结构。 4、链式存储结构中的结点包含____________域，_______________域 。 5、在栈的顺序实现中，栈顶指针top，栈为空条件______________。

6、允许在线性表的一端插入，另一端进行删除操作的线性表称为_______。插入的一端为______，删除的一端为______。

7、设有一个行优先顺序存储的数组A[5][6]，A[0][0]的地址为1100，且每个元素占2个存储单元，则A[2][3]的地址为_____________。

8、度数为0的结点，即没有子树的结点叫作__________结点或_________结点。同一个结点的儿子结点之间互称为___________结点。

四、程序题

1、写出下列程序段的输出结果。

void main( ){ Stack S; char x,y; InitStack(S); x=’c’;y=’k’;

push(S,x); push(S,’a’); push(S,y); pop(S,x); push(S,’t’); push(S,x); pop(S,x); push(S,’s’); while(!StackEmpty(S)){ pop(S,y);

printf(y);

};

printf(x); }

结果：_____________________

2、写出下列程序段的输出结果（队列中的元素类型QElem Type为char）。

void main( )

{

Queue Q; Init Queue (Q); Char x=’e’; y=’c’; EnQueue (Q,’h’); EnQueue (Q,’r’); EnQueue (Q,’y’);

DeQueue (Q,x); EnQueue (Q,x); DeQueue (Q,x); EnQueue (Q,’a’); while(!QueueEmpty(Q)) {

DeQueue (Q,y); printf(y); }; Printf(x);

}

结果：_____________________

3、完成下列程序,并说出该算法所完成的功能。 void weizhisort(struct node r[ n],int n) {

int low,high,mid,j,i; for(i=2;i<=n;i++) {

r[0]=r[i];

low= ___①____; high=___② ___; while(low<=high)

{

mid=(low+high)/2;

if(r[0].key

____③_______;

else

low=mid+1; }

for(j=i-1;j>=l;j--) r[j+1]=r[j]; r[low]=r[0]; } }

4、完成二叉树中序遍历的算法。

typedef struct node /* 链式存储的指针类型和结点定义 */ {

char data;

struct node *lchild,*rchild;