数据结构练习题--2011级--参考答案
选择题：
1.1数据结构在计算机内存中的表示是指：
A．数据的存储结构 B.数据结构
C．数据的逻辑结构 D.数据元素之间的关系
1.2数据的逻辑结构是指：
A. 数据所占的存储空间量
B．各数据元素之间的逻辑关系
C. 数据在计算机中顺序或链接的存储方式
D. 存储在内存或外存中的数据
1.3在下列的叙述中，正确的是：
A．数据的逻辑结构是指数据的各数据项之间的逻辑关系。
B．数据的物理结构是指数据在计算机内的实际存储形式。
C．在顺序存储结构中，数据元素之间的关系是显示体现的。
D．链接存储结构是通过结点的存储位置相邻来体现数据元素之间的关系。
填空题：
1.4
内容。
1.5
1.6
1.7
1.8表示关系。
1.9
1.10
简答题：
1.11数据结构研究的三方面内容之间有什么联系和区别？
数据结构研究的三方面内容包括: 数据的逻辑结构、存储结构和运算。数据的逻辑结构是数学模型，存储结构是指逻辑结构到存储区域的映射，运算是定义在逻辑结构上，实现在存储结构上。
1.12简述数据结构中讨论的三种经典结构的逻辑特征是什么？
三种经典结构：线性表、树和图。逻辑特征分别为：
（1）线性表：一对一。有且仅有一个开始结点和一个终端结点，其余的内部结点都有且仅有一个前趋结点和一个后继结点。
（2）树：一对多。有且仅有一个开始结点，可有若干个终端结点，其余的内部结点都有且仅有一个前趋结点，可以有若干个后继结点。
（3）图：多对多。可有若干个开始结点和终端结点，其余的内部结点可以有若干个前趋结点和若干个后继结点。
1.13简述各种常用存储方法的基本思想。
各种方法的基本思想：
顺序存储：逻辑上相邻的数据元素存储在物理位置上相邻的存储单元里。
链接存储：通过附加指针域表示数据元素之间的关系。
索引存储：除了存储数据元素，还要建立附加的索引表来标识数据元素的地址。
散列存储：根据关键字直接计算出该结点的存储地址，通常称为关键字－地址转换法。
选择题：
2.1线性表L=（a1，a2，…，a n），下列说法正确的是：
A. 每个元素都有一个直接前驱和一个直接后继。
B. 线性表中至少有一个元素。
C. 表中元素的排列顺序必须是由小到大或由大到小。
D. 除第一个和最后一个元素外，其余每个元素都有且仅有一个直接前驱和一个直接后继。
2.2下面关于线性表的叙述中，错误的是：
A．线性表若采用顺序存储，必须占用一片连续的存储单元
B．线性表若采用顺序存储，便于进行插入和删除操作
C．线性表若采用链接存储，不必占用一片连续的存储单元
D．线性表若采用链接存储，便于插入和删除操作
2.3在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为：
A .n-i+1
B .n-i
C .i
D .i-1
2.4删除长度为n的顺序表中的第i(1≤i≤n)个位置上的元素，元素的移动次数为：
A. n-i+1
B. n-i
C. i
D. i-1
2.5已知一个带头结点单链表L，在表头元素前插入新结点*s的语句为：
A. L=s; s->next=L;
B. s->next=L->next; L->next=s;
C. s=L; s->next=L;
D. s->next=L; s=L;
2.6已知一个不带头结点单链表的头指针为L，则在表头元素之前插入一个新结点*s的语句为：
A. L=s; s->next=L;
B. s->next=L; L=s;
C. s=L; s->next=L;
D. s->next=L; s=L;
2.7已知单链表上一结点的指针为p，则在该结点之后插入新结点*s的正确操作语句为：
A．p->next=s; s->next=p->next; B．s->next=p->next; p->next=s;
C．p->next=s; p->next=s->next; D．p->next=s->next; p->next=s;
2.8已知单链表上一结点的指针为p，则删除该结点后继的正确操作语句是：
A．s= p->next; p=p->next; free(s); B．p=p->next; free(p);
C．s= p->next; p->next=s->next; free(s); D．p=p->next; free(p->next);
2.9设一个链表最常用的操作是在表尾插入结点和在表头删除结点，则选用下列哪种存储结构效率最高？
A. 单链表
B. 双链表
C. 单循环链表
D. 带尾指针的单循环链表
2.10线性表的链接存储结构是一种（）存储结构。
A. 随机存取
B. 顺序存取
C. 索引存取
D. 散列存取
2.11链表不具备的特点是：
A. 插入删除不需要移动元素
B. 不必事先估计存储空间
C. 可随机访问任一结点
D. 所需空间与其长度成正比
填空题：
2.1在单链表L中，指针p
2.2判断带头结点的单链表L
2.12
2.13n个结点的单链表，已知一个结点的指针p
x
2.14
简答题：
2.15比较顺序表和链表这两种线性表不同存储结构的特点。
2.16简述头结点的作用。
头结点的作用是使得单链表在表头位置的插、删操作同中间位置的插、删操作完全相同。即使“空表”与“非空表”的操作统一，也使“表头结点”与其他位置结点的操作完全一致，无须特殊处理。
2.17写出单链表存储结构的C语言描述。
typedef int DataType;
typedef struct Node
{ DataType data;
struct Node *next;
}LinkList;
完善程序题：
2.18设计一个算法，其功能为：向一个带头结点的有序单链表（从小到大有序）中插入一个元素x，使插
入后链表仍然有序。请将代码补充完整。
typedef int DataType;
typedef struct Node
{ DataType data;
; /*定义指向该结构类型的指针变量next*/
}Linklist;
void insert(Linklist *L,DataType x)
{ Linklist *s,*p=L;
while(p->next && p->next->data ; /*p指针后移一步*/ ; /*申请一个新结点空间，将其地址赋给变量s*/ s->data=x; ; ; /*将*s结点插入到*p结点的后面*/ } 2.19设计一个函数功能为：在带头结点的单链表中删除值最小的元素。请将代码补充完整。 typedef int DataType; typedef Node /*定义结构体类型*/ { DataType data; struct Node * next; }LinkList; void deleteMin(LinkList *L) { LinkList *p=L->next,*q; /*首先查找值最小的元素，指针q指向最小元素结点*/ q=p; while(p) { if( p->data < q->data) q=p; ; /* p指针后移一步，比较单链表中的每一个结点*/ } if(!q) return; /*不存在最小结点（空表）时，直接退出*/ p=L; /*若存在最小结点，则先找到最小结点的前驱，即*q的前驱*/ while( ) p=p->next; ; /*从单链表中删除最小元素结点（指针q所指结点）*/ ; /* 释放指针q所指结点的空间*/ } 算法设计题： 2.20已知长度为n的线性表A中的元素是整数，写算法求线性表中值大于item的元素个数。分两种情况 编写函数：（1）线性表采用顺序存储；（2）线性表采用单链表存储。 （1）线性表采用顺序存储 #define MAX 1024 typedef int DataType; typedef struct { DataType data[MAX]; int last; } SeqList; int LocateElem (SeqList *L, DataType item) { int i,j=0; for(i=0;i<=L->last ;i++) if( L->data[i] >item ) j++; return j; } （2）线性表采用单链表存储 typedef int DataType; typedef struct Node { DataType data; struct Node *next; }LinkList; int locateElem(LinkList *L, DataType item ) { LinkList *p=L->next; int i=0; while ( p ) if( p->data >item) i++; return i ; } 2.21试写一算法实现对不带头结点的单链表H进行就地（不额外增加空间）逆置。 typedef int DataType; typedef struct Node { DataType data; struct Node *next; }LinkList; LinkList * Reverse(LinkList *L) { LinkList *p,*q; if (!L) return; p=H->next; q=H->next; L->next=NULL; while(q) {q=q->next; p->next= L; L=p; p=q;} return L; } 第3章 选择题： 3.1设一个栈的输入序列是1，2，3，4，5，则下列序列中，是栈的合法输出序列的是： A. 5 1 2 3 4 B. 4 5 1 3 2 C. 4 3 2 1 5 D. 3 5 2 4 1 3.2设有一顺序栈，元素1，2，3，4，5依次进栈，如果出栈顺序是2，4，3，5，1则栈的容量至少是： A .1 B. 2 C. 3 D. 4 3.3若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当入队一个元素， 再出队两个元素后，rear和front的值分别为： A. 1和5 B. 2和4 C. 4和2 D. 5和1 填空题： 3.4 3.5若序列a、b、c、d、e按顺序入栈，假设P表示入栈操作，S表示出栈操作，则操作序列PSPPSPSPSS 3.6已知一个顺序栈*s，栈顶指针是top，它的容量为， 3.7 3.8某循环队列的容量MAXSIZE=6，队头指针front=3，队尾指针rear=0 简答题： 3.9栈上的基本运算有哪些？ 栈的基本运算有： （1）初始化栈initStack（s）：构造了一个空栈s。 （2）判栈空empty（s）：若栈s为空栈，返回值为“真”（1），否则返回值为“假”（0）。 （3）入栈push（s，x）：在栈s的顶部插入一个新元素x，x成为新的栈顶元素。 （4）出栈pop（s）：删除栈s的栈顶元素。 （5）读栈顶元素top（s）：栈顶元素作为结果返回，不改变栈的状态。 3.10循环顺序队列的存储结构图示及C语言描述？ C语言描述：循环顺序队列图示： #define MAXSIZE 1024 Array typedef int DataType; typedef struct { DataType data[MAXSIZE]; int rear , front; }SeQueue; SeQueue *sq; front 3.11简述栈和队列有哪些联系与区别？ 栈和队列都是运算运算受限的线性表，逻辑结构相同；都可以顺序存储和链接存储，存储结构也相同；插入和删除运算都限制在线性表的表端完成，且不需要查找运算。 二者差别主要体现在运算的限制不同：栈是后进先出（LIFO）的线性表，限制它的插入和删除操作仅在表的一端进行。队列是先进先出（FIFO）的线性表，只允许在表的一端进行插入，而在表的另一端进行删除。 算法设计题： 3.12通常称正读和反读都相同的字符序列为“回文”，例如，“abcdeedcba”、“abcdcba”是回文。若字符序列 存储在一个单链表中，编写算法判断此字符序列是否为回文。（提示：将一半字符先依次进栈）#define maxsize 100 typedef char datatype1; typedef struct { datatype1 data[maxsize]; int top; } seqstack; typedef int datatype; typedef struct node { datatype data; struct node *next; } Linklist; Duichen(Linklist *head) { int i=1; Linklist *p; seqstack *s; s=initSeqStack(); p= head->next;n=0; while(p){n++; p=p->next;} p=head->next; while(i<=n/2) {push(s, p->data); i++; } if (n%2!=0) p=p->next; while(p&&p->data==pop(s)) p=p->next; if (p) return 0 else return 1; } 第5章 选择题： 5.1 设数据结构D-S 可以用二元组表示为D-S=(D ，S)，r ∈S ，其中： D={A ，B ，C ，D}， A ．线性结构 B ．树形结构 C ．图形结构 D ．集合 5.2 树最适合用来表示： A ．有序数据元素 B.无序数据元素 C ．元素之间具有分支层次关系的数据 D.元素之间无联系的数据 5.3 有关二叉树下列说法正确的是： A ．二叉树是度为2的有序树 B ．二叉树中结点的度可以小于2 C ．二叉树中至少有一个结点的度为2 D ．二叉树中任何一个结点的度都为2 5.4 深度为10的完全二叉树，第3层上的的结点数是： A .15 B .16 C . 4 D .32 5.5 设一棵树的度为4，其中度为1、2、3、4的结点个数分别为6、3、2、1，则这棵树中叶子结点的个 数为： A .8 B. 9 C. 10 D. 11 5.6 对于二叉树来说，第i 层上最多包含的结点个数为： A ．2i - 1 B. 2i + 1 C ．2i D.2i 5.7 树的后根遍历序列等同于与该树对应的二叉树的哪种序列？ A. 前序序列 B. 中序序列 C. 后序序列 D. 层序序列 5.8 设森林F 中有三棵树，第一，第二，第三棵树的结点个数分别为M 1，M 2和M 3。与森林F 对应的二 叉树根结点的右子树上的结点个数是： A ．M 1 B ．M 1+M 2 C ．M 3 D ．M 2+M 3 填空题： 5.9 二叉树具有10个度为2的结点，5个度为1的结点，则度为0 5.10 包含n 2log 1n ??+?? 。 5.11 某完全二叉树共有2001的结点。 5.12 一棵高度为10 5.13 某完全二叉树结点按层顺序编号（根结点的编号是1），若21号结点有左孩子结点，则它的左孩子结 点的编号为。 5.14 深度为k 5.15 n 简答题： 5.16画出包含三个结点的树和二叉树的所有不同形态。 5.17找出满足下面条件的二叉树： （1）前序遍历与中序遍历结果相同：只有右分支的单分支二叉树 （2）前序遍历和后序遍历结果相同：只有一个根结点的二叉树 （3）中序遍历和后序遍历结果相同：只有左分支的单分支二叉树 5.18一棵二叉树的中序、后序遍历序列分别为：G L D H B E I A C J F K和L G H D I E B J K F C A，请 回答： （1）画出二叉树逻辑结构的图示。 （2）画出此二叉树的二叉链表存储结构的图示并给出C语言描述。 （3）画出上题中二叉树的中序线索二叉树。 （4）画出中序线索二叉链表存储结构图示并给出C语言描述。 （1）二叉树的逻辑结构图示： A B C H E D F G I K J L （2）二叉链表存储结构的图示及C语言描述： typedef char DataType; typedef struct Node { DataType data; struct Node *lchild,*rchild; }BiTree; （3）中序线索二叉树： （4）中序线索二叉链表的图示及C 语言描述： typedef char DataType; typedef struct Node { DataType data; struct Node *lchild,*rchild; int ltag,rtag; }BiThrTree; 5.19 设有森林如图5.31所示，请回答： （1）画出与该森林对应的二叉树的逻辑结构图示。 （2）写出该二叉树的前序、中序、后序遍历序列。 （3）画出该二叉树的中序线索二叉链表的图示并给出C 语言描述。 E H A B C D F G 图5.31 （1）二叉树的逻辑结构图示： （2）前序遍历序列：ABCDFGEH ， 中序遍历序列：ADGFCBHE 后序遍历序列：GFDCHEBA （3）中序线索二叉链表的图示及C 语言描述： typedef char DataType; typedef struct Node { DataType data; struct Node *lchild,*rchild; int ltag,rtag; }BiThrTree; A C B F D E G H 5.20 设有森林 B=(D,S), D={A,B,C,D,E,F,G,H,I,J}, r ∈S r={ （3）画出此二叉树的二叉链表存储结构的图示并给出C 语言描述。 （1）与森林对应的二叉树的逻辑结构图示： （2）前序遍历序列：ABECFDGHIJ ， 中序遍历序列：EBFCDAHJIG 后序遍历序列：EFDCBJIHGA （3）二叉链表存储结构的图示及C 语言描述： typedef char DataType; typedef struct Node { DataType data; struct Node *lchild,*rchild; }BiTree; 5.21 请画出5.32中的各二叉树对应的森林。 A F G E C B D A C B A A B C H J I （a ） （b ） （c ） （d ） 图5.32 A A B C （a ） （b ） （c ） （d ） A B C A G E B D H J C F I A H G D C J B I E F 5.22 假设用于通信的电文由字符集{a ，b ，c ，d ，e ，f ，g ，h}中的字母构成，这8个字母在电文中出现的 概率分别为{0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10}，试为这8个字母进行哈夫曼编码。请回答： （1）画出哈夫曼树（按根点权值左小右大的原则）。 （2）写出依此哈夫曼树对各个字母的哈夫曼编码。 （3）求出此哈夫曼树的带权路径长度WPL 。 （1）哈夫曼树： （2）各字母的哈夫曼编码： a:1010 b:00 c:10000 d:1001 e:11 f:10001 g:01 h:1011 （3）哈夫曼树的带权路径长度WPL ： 1 n i i i W PL w l == ∑ =0.07×4+0.19×2+0.02×5+0.06×4+0.32×2+0.03×5+0.21×2+0.10×4=2.61 完善程序题： 5.23 设计一个算法，其功能为：利用中序线索求结点的中序后继。请将代码补充完整。 typedef char DataType; typedef struct Node { DataType data; struct Node *lchild, ; int ltag,rtag; }BiThrTree; BiThrTree * InOrderNext(BiThrTree *p) /* 求中序后继 */ { if( ) p=p->rchild; /*若结点*p 无右孩子 */ else{ /*若结点*p 有右孩子 */ ; while(p->ltag==0) ; } return ; 第6章 选择题： 6.1 n 个顶点的有向图中有向边的数目最多为： A ． n-1 B ． n C ． n(n-1)/2 D ． n(n-1) 6.2 下面哪一方法可以判断出一个有向图是否有环（回路）： A ．深度优先遍历 B. 求最短路径 C. 拓扑排序 D. 广度优先遍历 填空题： 6.3 A= 0 1 0 1 0 1 1 0 1 0 1 1 0 1 0 0 0 1 1 0 0 0 1 1 0 1 0 1 0 0 1 1 1 1 0 0 6.4 在无向图的邻接矩阵存储结构中，第i v i 矩阵中，第i 列上非零元素的个数是顶点v i 6.5 6.6 对于一个具有n 个顶点和e 简答题： 6.7 设一个有向图为G=(V ,E)，其中V={ v 1,v 2,v 3,v 4}，E={< v 2,v 1>,< v 2,v 3>,< v 4,v 1>,< v 1,v 4>,< v 4,v 2>}，请回 答下列各问： （1）画出该有向图，求出每个顶点的入度和出度。 （2）画出该图的邻接矩阵存储结构图示。 （3）对（2）中的邻接矩阵，给出从顶点v 2出发的DFS 序列和DFS 生成树。 （4）对（2）中的邻接矩阵，给出从顶点v 2出发的BFS 序列和BFS 生成树。 （1）有向图： 顶点v 1的入度是2，出度是1； 顶点v 2的入度是1，出度是2； 顶点v 3的入度是1，出度是0； 顶点v 4的入度是1，出度是2。 （2）邻接矩阵存储结构图示： A 1= 0 0 0 11 0 1 00 0 0 0 1 1 0 0 r 1 （3）DFS 序列： v 2, v 1,v 4,v 3 （4）BFS 序列： v 2, v 1,v 3,v 4 生成树： 生成树： 6.8 对图6.44所示的无向图，依次输入各边：(v 1,v 2)、(v 1,v 4)、(v 2,v 3)、(v 3,v 4)、(v 3,v 5)，请回答下列各问： （1）写出该无向图的二元组表示。 （2）画出该图的邻接表（头插法建表）存储结构图示。 （3）对（2）中的邻接表，给出从顶点v 1出发的DFS 序列和DFS 生成树。 （4）对（2）中的邻接表，给出从顶点v 1出发的BFS 序列和BFS 生成树。 （1）无向图的二元组表示： 设G =(V ,E )，V 为顶点集，E 为边集，则 V ={v 1,v 2,v 3,v 4,v 5} E ={(v 1,v 2)、(v 1,v 4)、(v 2,v 3)、(v 3,v 4)、(v 3,v 5)} （2）图的邻接表（头插法建表）存储结构图示： 012345 vertex link 顶点表 边表 （3）从顶点v 1出发： （4）从顶点v 1出发： DFS 序列：v 1,v 4,v 3,v 5,v 2 BFS 序列：v 1,v 4,v 2,v 3,v 5 DFS 生成树： BFS 生成树： 画出图6.45中所有可能的最小生成树。 图6.44 图6.45 6.1 图6.45的所有可能的最小生成树： 第7章 选择题： 7.1在对n个元素进行起泡排序的过程中，最好情况下的时间复杂度为： A ．O(n3) B．O(n2) C．O(n) D．O(1) 7.2堆排序属于下列哪类排序？ A. 插入 B. 交换 C. 归并 D. 选择 7.3下列哪组序列是堆： A．(79,40,46,56,38,84) B. (84,56,79,46,38,40) C．(40,38,46,56,79,84) D. (84,38,46,40,56,79) 7.4下列排序算法中，哪种排序方法在一趟结束后不一定能选出一个元素放在其最终位置上。 A. 简单选择排序 B. 冒泡排序 C. 归并排序 D. 堆排序 7.5就平均性能而言，目前最好的内排序方法是： A. 冒泡 B. 希尔插入 C. 交换 D. 快速 7.6在下面的排序方法中，平均时间复杂度为O(n2)且是不稳定的排序方法为： A. 快速排序 B. 直接插入排序 C. 直接选择排序 D. 起泡排序 填空题： 7.7 7.8 7.9设记录的排序码序列为：（49，38，65，97，76，13，27），若采用快速排序，则第一趟划分的结果为 7.10快速排序、 7.11 7.12 速排序方法。 7.13 简答题： 7.14常用的实现排序的方法有几大类？它们的实现思想是什么？ 插入排序的基本思想是： 将一个待排序记录按照排序码的大小插入到一个有序序列的适当位置，使得插入后的序列仍然有序，直到所有记录全部插入到有序序列中。 交换排序的基本思想是： 两两比较待排序记录的排序码，不符合排列顺序则交换记录，直到所有记录的排序码都符合排序要求。 选择排序的基本思想是： 每一次从待排序记录序列中选取一个排序码最小（或最大）的记录，放在待排序记录序列的最前面（或最后面），重复此过程，直到所有的记录按排序码排好序。 归并排序的基本思想是： 利用“归并”技术实现的排序方法。所谓归并就是将两个或多个有序表合并成一个有序表的过程。如果是将两个有序表合并成一个有序表称为二路归并，二路归并是最简单和最常用的。 基数排序的基本思想是： 基数排序是基于排序码的结构分解，然后通过“分配”和“收集”方法实现的排序。 7.15给定排序码的序列{39、33、13、15、58、41、27、46、23}。请回答： （1）采用希尔（Shell）排序（步长分别为5,3,1），写出各趟排序结果。 （2）采用快速排序的方法进行排序，写出各趟排序结果。 （1）希尔排序： 39 33 13 15 58 41 27 46 23 （初始） 39 27 13 15 58 41 33 46 23 （1趟希尔排序结果） 15 27 13 33 46 23 39 58 41 （2趟希尔排序结果） 13 15 23 27 33 39 41 46 58 （3趟希尔排序结果） （2）快速排序： 39 33 13 15 58 41 27 46 23 （初始） {23 33 13 15 27} 39 {41 46 58} （1层划分结果） {15 13} 23 {33 27} 39 41 {46 58} （2层划分结果） {13} 15 23 {27} 33 39 41 46 {58} （3层划分结果） 7.16判断下列序列是否为堆？如果不是，则把它们调整成堆。 （1）（503，87，512，61，908，170，896，275，653，462） （2）（12，70，33，65，24，48，92，86，33，55） （3）（100，55，97，30，23，86，60，8，12） （4）（5，56，18，40，38，27，58，30，78，28，98） （1）不是堆，调整为大根堆：（908，653，896，503，462，170，512，275，61，87）（2）不是堆，调整为小根堆：（12，24，33，33，55，48，92，86，65，70） （3）是大根堆 （4）不是堆，调整为小根堆：（5，28，18，30，38，27，58，40，78，56，98） 7.17设待排序文件各个记录的排序码序列为：19、23、2、67、39、91、43、25，进行堆排序，请回答： （1）画出初始建成的大根堆对应的完全二叉树。 （2）写出初始大根堆序列。 （3）画出第一趟堆排序后对应的完全二叉树。 （1）初始建成的大根堆（3）第一趟堆排序后对应的完全二叉树 （2）初始大根堆序列：91 67 43 25 39 2 19 23 完善程序题： 7.18设计一个算法，其功能为：利用直接插入排序的方法，将一组存储在带头结点的单链表中的记录递增 排序。请将算法补充完整。 typedef struct node { int key; DataType other; ; /* 定义单链表的指针域next */ } LinkList; void insertSort(LinkList *L) { LinkList *p,*q,*s; p=L->next; L->next=NULL; while(p) { q=L; while(q->next && ) /* 指针q从头开始查找，寻找合适的插入位置*/ ; s=p->next; ; /* 将指针p所指的结点插入到q之后*/ ; p=s; } } 第8章 选择题： 8.1对线性表进行二分查找时，要求线性表必须： A．以顺序方式存储B．以顺序方式存储，且按关键字有序 C．以链接方式存储D．以链接方式存储，且按关键字有序 8.2顺序查找法适合于存储结构为（）的线性表。 A．散列存储B．顺序存储或链接存储C．压缩存储D．索引存储 8.3若结点的存储地址与其关键字之间存在某种函数关系，则称这种存储结构为： A.顺序存储结构 B.链式存储结构 C.索引存储结构 D.散列存储结构 8.4下面关于散列查找的说法正确的是： A．在采用线性探测法处理冲突的散列表中，同义词在表中一定相邻； B．除留余数法是所有散列函数中最好的； C．在散列表中进行查找，“比较”次数的多少与冲突有关； D．散列函数构造的越复杂越好，因为这样随机性好，冲突小。 填空题： 8.5对于n个元素的顺序表采用顺序查找，且使用监视哨。若查找成功，则比较关键字的次数最多为 8.6在有序表（9,10,14,18,23,27,30,32,42）中，用二分法查找关键字值32（成功），需做的关键字比较次 35（失败），需做的关键字比较次数为 8.7具有8个关键字的有序表，二分法查找成功的平均查找长度(ASL 8.8 8.9 8.10 已知二叉排序树的左右子树均不为空， 上所有结点的值均大于它的根结点的值。 8.11 依次插入关键字（51， 37，60，54 32，79，27，36 ）生成二叉排序树，则查找关键字值54（查 找成功）22（查找失败），需做的关键字比较次数为 简答题： 8.12 将关键字（45，87，30，33，63，27，51，76）依次插入到一棵初始为空的二叉排序树中。请回答： （1）画出对应的二叉排序树。 （2）并求出等概率情况下查找成功时的平均查找长度。 （3）若在二叉排序树中插入新的关键字60，则为寻找插入位置，分别与哪些关键字进行比较。 （1）二叉排序树： （2）等概率情况下查找成功时的平均查找长度： ASL 成功=(1*1+2*2+3*3+4*2)/8=11/4 （3）若在二叉排序树中插入新的关键字60，则为寻找插入位置，分别与关键字45,87,63,51 进行比较。 8.13 设散列表的长度为16，散列函数为H （k ）=k%13，用线性探测法处理冲突，依次插入关键字：19， 01，13，23，24，55，20，84，27，68，11，10，77。请回答： （1）画出散列表示意图并给出查找每个关键字时需要比较的次数。 （2）查找关键字98（失败）时，需要依次与哪些关键字比较。 （3）求等概率下查找成功的平均查找长度ASL 。 （1）构造的散列表如下： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 下标 比较次数 1 1 1 1 1 1 1 3 2 2 2 4 3 （2）查找关键字98时，需要依次与哪些关键字比较。 答：分别于关键字20,84比较。 （3）等概率下查找成功的平均查找长度ASL ： ASL 成功=(1+1+2+1+2+1+1+3+1+1+2+4+3)/13=23/13 8.14 设关键字序列为（71，12，88，53，11，25，65，27，16），散列函数为H （key ）= key % 7，采用链 地址法解决冲突。请回答： （1）画出散列表示意图（用头插法向单链表中插入结点）。 （2）查找关键字88时，需要依次与哪些关键字比较。 （3）求等概率下查找成功的平均查找长度ASL 。 （1）散列表： 1 2 3 4 5 6 （2）查找关键字88时，分别与25,11,53,88比较。 =（1*5+2*2+3*1+4*1）=16/9 （3）ASL 成功 全国2011年1月高等教育自学考试 数据结构试题 课程代码：02331 一、单项选择题（本大题共15小题，每小题2分，共30分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.下列选项中与数据存储结构无关的术语是（） A.顺序表 B.链表 C.链队列 D.栈 2.将两个各有n个元素的有序表归并成一个有序表，最少的比较次数是（） A.n-1 B.n C.2n-1 D.2n 3.已知循环队列的存储空间大小为m，队头指针front指向队头元素，队尾指针rear指向队尾元素的下一个位置，则 向队列中插入新元素时，修改指针的操作是（） A.rear=(rear-1)%m; B.front=(front+1)%m; C.front=(front-1)%m; D.rear=(rear+1)%m; 4.递归实现或函数调用时，处理参数及返回地址，应采用的数据结构是（）？？？？ A.堆栈 B.多维数组 C.队列 D.线性表 5.设有两个串p和q，其中q是p的子串，则求q在p中首次出现位置的算法称为（）p55 A.求子串 B.串联接 C.串匹配 D.求串长 6.对于广义表A，若head(A)等于tail(A)，则表A为（）p66 A.( ) B.(( )) C.(( ),( )) D.(( ),( ),( )) 7.若一棵具有n(n>0)个结点的二叉树的先序序列与后序序列正好相反，则该二叉树一定是（） A.结点均无左孩子的二叉树 B.结点均无右孩子的二叉树 C.高度为n的二叉树 D.存在度为2的结点的二叉树 8.若一棵二叉树中度为l的结点个数是3，度为2的结点个数是4，则该二叉树叶子结点的个数是（）p73 A.4 B.5 C.7 D.8 9.下列叙述中错误的是（）108 A.图的遍历是从给定的源点出发对每一个顶点访问且仅访问一次107 B.图的遍历可以采用深度优先遍历和广度优先遍历108 C.图的广度优先遍历只适用于无向图 D.图的深度优先遍历是一个递归过程108 10.已知有向图G=(V，E)，其中V={V1，V2，V3，V4}，E={ 第1章绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据 类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解： ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={ 图 1. 填空题 ⑴ 设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。 【解答】0，n(n-1)/2，0，n(n-1) 【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。 ⑵ 任何连通图的连通分量只有一个，即是（）。 【解答】其自身 ⑶ 图的存储结构主要有两种，分别是（）和（）。 【解答】邻接矩阵，邻接表 【分析】这是最常用的两种存储结构，此外，还有十字链表、邻接多重表、边集数组等。 ⑷ 已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（）。 【解答】Ｏ(n+e) 【分析】在无向图的邻接表中，顶点表有n个结点，边表有2e个结点，共有n+2e个结点，其空间复杂度为Ｏ(n+2e)=Ｏ(n+e)。 ⑸ 已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。 【解答】求第j列的所有元素之和 ⑹ 有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。 【解答】出度 ⑺ 图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。 【解答】前序，栈，层序，队列 ⑻ 对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal 算法求最小生成树的时间复杂度为（）。 【解答】Ｏ(n2)，Ｏ(elog2e) 【分析】Prim算法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树；Kruskal算法采用边集数组做存储结构，适合于求稀疏图的最小生成树。 ⑼ 如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。 【解答】回路 ⑽ 在一个有向图中，若存在弧、、，则在其拓扑序列中，顶点vi, vj, vk的相对次序为（）。 【解答】vi, vj, vk 【分析】对由顶点vi, vj, vk组成的图进行拓扑排序。 2. 选择题 ⑴ 在一个无向图中，所有顶点的度数之和等于所有边数的（）倍。 A 1/2 B 1 C 2 D 4 【解答】C 【分析】设无向图中含有n个顶点e条边，则。 数据结构试题及答案 一、单项选择题 (1)一个算法应该就是（)。 A)程序???B）问题求解步骤得描述 C）要满足五个基本属性??D) A与C (2)算法指得就是（)。 A）计算机程序???B）解决问题得计算方法 C)排序算法???D）解决问题得有限运算序列。 (3)与数据元素本身得形式、内容、相对位置、个数无关得就是数据得(）。 A) 存储结构B) 逻辑结构C）算法D)操作 (4)从逻辑上可以把数据结构分为( ）两大类。 A）动态结构、静态结构??B) 顺序结构、链式结构 C）线性结构、非线性结构???D）初等结构、构造型结构 (5)下列叙述中正确得就是(）。 A)一个逻辑数据结构只能有一种存储结构 B）数据得逻辑结构属于线性结构,存储结构属于非线性结构 C）一个逻辑数据结构可以有多种存储结构,且各种存储结构不影响数据处理得效率 D）一个逻辑数据结构可以有多种存储结构,且各种存储结构影响数据处理得效率 (6)数据得基本单位就是（） ?A) 数据项??B) 数据类型C)数据元素??D)数据变量 (7)下列程序得时间复杂度为（) i=０；s＝０; wｈｉlｅ(s 1 绪论沈阳理工大学应用技术学院信息与控制学院 计算机科学与技术教研室 2011-5-8 数据结构复习题：绪论 单选题 1、在数据结构中，与所使用的计算机无关的数据叫_____结构。 A存储|B物理|C逻辑|D物理和存储 2、在数据结构中，从逻辑上可以把数据结构分成______。 A动态结构和静态结构|B紧凑结构和非紧凑结构|C线性结构和非线性结构|D内部结构和外部结构图 3、数据结构在计算机内存中的表示是指_______。 数据的存储结构|数据结构|数据的逻辑结构|数据元素之间的关系 4、在数据结构中，与所使用的计算机无关的是数据的______结构。 逻辑|存储|逻辑和存储|物理 5、在以下的叙述中，正确的是_____。 线性表的线性存储结构优于链表存储结构|二维数组是其数据元素为线性表的线性表|栈的操作方式是先进先出|队列的操作方式是先进后出 6、在决定选取何种存储结构时，一般不考虑_______。 各结点的值如何|结束个数的多少|对数据有哪些运算|所用编程语言实现这种结构是否方便 7、在存储数据时，通常不仅要存储各数据元素的值，而且还要存储_______。 数据的处理方法|数据元素的类型|数据元素之间的关系|数据的存储方法 8、下面说法错误的是_______。 (1)算法原地工作的含义是指不需要任何额外的辅助空间 (2)在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 (3)所谓时间复杂度是指最坏情况下，估计算法执行时间的一个上界 (4)同一个算法，实现语句的级别越高，执行效率越低 (1)|(1)、(2)|(1)、(4)|(3) 9、通常要求同一逻辑结构中的所有数据元素具有相同的特性。这意味着______。 数据元素具有同一特点|不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致|每个数据元素都一样|数据元素所包含的数据项的个数要相等 10、以下说法正确的是_______。 数据元素是数据的最小单位|数据项是数据的基本单位|数据结构是带结构的数据项的集合|一些表面上很不相同的数据可以有相同的逻辑结构 11、____是数据的最小单元,_____是数据的基本单位. 数据项|数据元素|信息项|表元素 12、数据结构是指_____以及它们之间的_____. (1)数据元素(2)结构|(1)计算方法(2)关系|(1)逻辑存储(2)运算|(1)数据映像(2)算法 13、计算机所处理的数据一般具备某种内在的关系,这是的指_____. 数据和数据之间存在的某种关系|元素和元素之间存在某种关系|元素内部具有某种结构|数据项和数据项之间存在某种关系 14、数据的逻辑结构可以分为_____两类. 动态结构和表态结构|紧凑结构和非紧凑结构|线性结构和非线性结构|内部结构和外部结构 15、数据的逻辑结构是指_____关系的整体. 数据元素之间逻辑|数据项之间逻辑|数据类型之间|存储结构之间 16、在存储数据时,通常不仅要存储各数据元素的值,而且还要存储_____. 数据的处理方法|数据元素的类型|数据元素之间的关系|数据的存储方法 习题1 一、单项选择题 A1.数据结构是指（）。 A.数据元素的组织形式 B.数据类型 C.数据存储结构 D.数据定义 C2.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（）。 A.存储结构 B.逻辑结构 C.链式存储结构 D.顺序存储结构 D3.树形结构是数据元素之间存在一种（）。 A.一对一关系 B.多对多关系 C.多对一关系 D.一对多关系 B4.设语句x++的时间是单位时间，则以下语句的时间复杂度为（）。 for(i=1; i<=n; i++) for(j=i; j<=n; j++) x++; A.O(1) B.O(2n) C.O(n) D.O(3n) CA5.算法分析的目的是（1），算法分析的两个主要方面是（2）。 （1） A.找出数据结构的合理性 B.研究算法中的输入和输出关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 （2） A.空间复杂度和时间复杂度 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 6.计算机算法指的是（1），它具备输入，输出和（2）等五个特性。 （1） A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 （2） A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性 C.确定性，有穷性和稳定性 D.易读性，稳定性和安全性 7.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（）。 A.低 B.高 C.相同 D.不好说 8.数据结构作为一门独立的课程出现是在（）年。 A.1946 B.1953 C.1964 D.1968 9.数据结构只是研究数据的逻辑结构和物理结构，这种观点（）。 A.正确 B.错误 C.前半句对，后半句错 D.前半句错，后半句对 一．是非题 1. 数据结构(应该是抽象数据类型)可用三元式表示(D，S，P)。其中：D是数据对象，S是D上的关系，P是对D的基本操作集。(f) 2 简单地说,数据结构是带有结构的数据元素的集合。(t) 3 判断带头结点的非空循环单链表(头指针为L)中指针p所指结点是最后一个元素结点 的条件是：p->next==L。(t) 4 线性表的链式存储结构具有可直接存取表中任一元素的优点。(f) 5 线性表的顺序存储结构优于链式存储结构。(f) 6. 在单链表P指针所指结点之后插入S结点的操作是： P->next= S ; S-> next = P->next;。(f) (顺序弄反了S-> next = P->next; P->next= S ;) 7 对于插入、删除而言，线性表的链式存储优于顺序存储。(t) 8. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。(f) 9. 栈和队列是操作上受限制的线性表。(t) 10. 队列是与线性表完全不同的一种数据结构。(f) (栈和队列是操作上受限制的线性表) 11. 队列是一种操作受限的线性表，凡对数据元素的操作仅限一端进行。(f) (两端) 12. 栈和队列也是线性表。如果需要，可对它们中的任一元素进行操作。(f) ( “如果需要,可对它们中的任一元素进行操作.” 这里的意思是在O(1)的时间来读和改某个元素。比如数组的直接索引。 栈：如果需要，每一次只能对栈顶的元素进行操作 队列：如果需要，每一次只能对两端，或者只能对队列头的元素进行操作。) 13. 栈是限定仅在表头进行插入和表尾进行删除运算的线性表。(f) 14. 二叉树中每个结点有两个子结点，而对一般的树，则无此限制，所以，二叉树是树的特殊情形。(f) (二叉树和树相互独立) 15 二叉树是一棵结点的度最大为二的树。(f) (二叉树和树相互独立) 16 赫夫曼树中结点个数一定是奇数。(t) 17 在二叉树的中序遍历序列中，任意一个结点均处在其左孩子结点的后面。(t) (LDR) 18 假设B是一棵树，B′是对应的二叉树。则B的后根遍历相当于B′的后序遍历。(f) (后根遍历相当于中序遍历) 19. 通常，二叉树的第i层上有2i-1个结点。(f) (应该为1~2i-1个) 20. 中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。(t) 21 二叉树的先序遍历序列中，任意一个结点均处在其孩子结点的前面。(t) 22 由树结点的先根序列和后根序列可以唯一地确定一棵树。(t) 23 邻接多重表可以用以表示无向图，也可用以表示有向图。(f) (只能表示无向图，有向图用十字链表) 24 可从任意有向图中得到关于所有顶点的拓扑次序。(f) (带环图没有) 25 有向图的十字链表是将邻接表和逆邻接表合二为一的链表表示形式。(t) 《数据结构》题库及答案 一、选择题 1．线性表的顺序存储结构是一种 的存储结构，线性表的链式存储结构是一种 的存储结构。 a. 随机存储； b.顺序存储； c. 索引存取； d. HASH 存取 2．一个栈的入栈序列是a,b,c,d,e ，则栈的不可能的输出序列是 。 a. edcba; b. decba; c. dceab; d.abcde 3．一个队列的入队序列是1，2，3，4，则队列的输出序列是 。 a. 4,3,2,1; b. 1,2,3,4; c. 1,4,3,2; d.3,2,4,1 4．在一个单链表中，已知p 结点是q 结点的直接前驱结点，若在p 和q 之间插入结点s ，则执行的操作是 。 a. s->nxet=p->next; p->next=s; b. p->next=s->next; s->next=p; c. q->next=s; s->next=p; d. p->next=s; s->next=q; 5．设有两个串p,q ，求q 在p 中首次出现的位置的运算称作 。 a.联接 b.模式匹配 c.求子串 d.求串长 6．二维数组M 的成员是6个字符（每个字符占一个存储单元）组成的串，行下标i 的范围从0到8，列下标j 的范围从1到10，则存放M 至少需要 个字节。 a. 90 b.180 c.240 d.540 7．在线索二叉树中，结点p 没有左子树的充要条件是 。 a. p->lch==NULL b. p->ltag==1 c. p->ltag==1且p->lch=NULL d. 以上都不对 8．在栈操作中，输入序列为（A ，B ，C ，D ），不可能得到的输出序列为：______ A 、（A ， B ， C ， D ） B 、（D ，C ，B ，A ） C 、（A ，C ，D ，B ） D 、（C ，A ，B ，D ） 9．已知某二叉树的后序序列是dabec ，中序序列是debac ，则它的先序序列是 。 A 、acbed B 、decab C 、deabc D 、cedba 10．设矩阵A 是一个对称矩阵，为了节省存储空间，将其下三角部分（见下图）按行序存放在一维数组B[1..n(n-1)/2]中，对任一上三角部分元素)(j i a ij ，在一维数组B 的存放位置是 。 第1章概论 1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的①Ｃ、数据信息在计算机中的②A以及一组相关的运算等的课程。 ①A．操作对象Ｂ．计算方法Ｃ．逻辑结构Ｄ．数据映象 ②A．存储结构Ｂ．关系Ｃ．运算Ｄ．算法 2. 计算机算法指的是① C ，它必具备输入、输出和② B 等五个特性。 ① A. 计算方法 B. 排序方法 C. 解决问题的有限运算序列 D. 调度方法 ② A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和安全性 3.下面程序段的时间复杂度是D for(i=0;i 图 1. 填空题 ⑴设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。 【解答】0，n(n-1)/2，0，n(n-1) 【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。 ⑵任何连通图的连通分量只有一个，即是（）。 【解答】其自身 ⑶图的存储结构主要有两种，分别是（）和（）。 【解答】邻接矩阵，邻接表 【分析】这是最常用的两种存储结构，此外，还有十字链表、邻接多重表、边集数组等。 ⑷已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（）。 【解答】Ｏ(n+e) 【分析】在无向图的邻接表中，顶点表有n个结点，边表有2e个结点，共有n+2e个结点，其空间复杂度为Ｏ(n+2e)=Ｏ(n+e)。 ⑸已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。 【解答】求第j列的所有元素之和 ⑹有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。 【解答】出度 ⑺图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。 【解答】前序，栈，层序，队列 ⑻对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal 算法求最小生成树的时间复杂度为（）。 【解答】Ｏ(n2)，Ｏ(elog2e) 【分析】Prim算法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树；Kruskal算法采用边集数组做存储结构，适合于求稀疏图的最小生成树。 ⑼如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。 【解答】回路 ⑽在一个有向图中，若存在弧、、，则在其拓扑序列中，顶点vi, vj, vk的相对次序为（）。 【解答】vi, vj, vk 单选题(每题2分，共20分) 1. 1. 对一个算法的评价，不包括如下(B )方面的内容。 A .健壮性和可读性 B .并行性 C .正确性 D .时空复杂度 2.2. 在带有头结点的单链表HL 中，要向表头插入一个由指针 p 指向 的结点，则执行(A )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; 都具有相同的(A )。 A.行号 B .列号 C .元素值 D .非零元素个数 9. 快速排序在最坏情况下的时间复杂度为(D )。 A. O(log 2n) B . O(nlog 2n) C . 0(n) D 10.10. 从二叉搜索树中查找一个元素时，其时间复杂度大致 为 A. O(n) B. O(1) C. O(log 2 n) D. O(n 二、 运算题(每题6分，共24分) 1. 1. 数据结构是指数据及其相互之间的 _________________ 。当结点之 间存在M 对N (M N)的联系时，称这种结构为 __________________________ 。 2. 2. 队列的插入操作是在队列的_ _尾 ________ 行，删除操作是在队 列的 ____ 首 _____ 行。 3. 3. 当用长度为N 的数组顺序存储一个栈时，假定用top==N 表示栈 C. p->next=HL; p=HL; 3. 3. A. C. D. HL=p; p-> next=HL; 对线性表，在下列哪种情况下应当采用链表表示? 经常需要随机地存取元素 B. 表中元素需要占据一片连续的存储空间 一个栈的输入序列为1 2 3， 4. 4. 列的是(C ) A. 2 3 1 C. 3 1 2 AOV 网 是一种(D ) 有向 图 B .无向图 (B ) 经常需要进行插入和删除操作 D.表中元素的个数不变 则下列序列中不可能是栈的输出序 B. 3 2 1 5. 5. 6. .无向无环图 D .有向无环图 采用 开放定址法处理散列表的冲突时，其平均查找长度( B. 高于链接法处理冲突 D .高于二分查找 7. 8. 6. A.低于链接法处理冲突 .与链接法处理冲突相同 7. 参数。 A.值 8. B)。 若需要利用形参直接访问实参时，应将形参变量说明为( B .函数 C .指针 D .引用 在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点 9. .0(n 2) (C )。 2 ) 第十一章文件 一、选择题 1. 散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址，因为散列函数是一对一的关系，则选择好的（）方法是散列文件的关键。【哈尔滨工业大学 2001二、5 （2分）】 A. 散列函数 B. 除余法中的质数 C. 冲突处理 D. 散列函数和冲突处理 2. 顺序文件采用顺序结构实现文件的存储，对大型的顺序文件的少量修改，要求重新复制整个文件，代价很高，采用（）的方法可降低所需的代价。【北京邮电大学 2000 二、 8 （20/8分）】 A. 附加文件 B. 按关键字大小排序 C. 按记录输入先后排序 D. 连续排序 3. 用ISAM组织文件适合于（）。【中科院软件所 1998】 A．磁带 B．磁盘 4．下述文件中适合于磁带存储的是（）。【中科院计算所 2000 一、7（2分）】 A. 顺序文件 B. 索引文件 C. 散列文件 D. 多关键字文件 5. 用ISAM和VSAM组织文件属于（）。 A. 顺序文件 B. 索引文件 C. 散列文件 【中国科技大学 1998 二、5（2分）中科院计算所 1998 二、5（2分）】 6. ISAM文件和VASM文件属于（）。【山东大学 2001 二、5 (1分)】 A. 索引非顺序文件 B. 索引顺序文件 C. 顺序文件 D. 散列文件 7. B+树应用在（）文件系统中。【北京邮电大学 2001 一、1（2分）】 A. ISAM B. VSAM 二、判断题 1. 文件是记录的集合，每个记录由一个或多个数据项组成，因而一个文件可看作由多个记录组成的数据结构。【长沙铁道学院 1998 一、5 (1分)】 2. 倒排文件是对次关键字建立索引。【南京航空航天大学 1997 一、10（1分）】 3. 倒排序文件的优点是维护简单。【南京航空航天大学 1995 五、10（1分）】 4. 倒排文件与多重表文件的次关键字索引结构是不同的。【西安交通大学 1996 二、6 (3分)】 5. Hash表与Hash文件的唯一区别是Hash文件引入了‘桶’的概念。【南京航空航天大学1996六10(1分）】 6. 文件系统采用索引结构是为了节省存储空间。【北京邮电大学 2000 一、10 （1分）】 7. 对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方法。 【东南大学 2001 一、1-10 （1分）】 8. 对磁带机而言，ISAM是一种方便的稳健组织方法。【中科院软件所 1997 一、10（1分）】 9. 直接访问文件也能顺序访问，只是一般效率不高。【北京邮电大学 2002 一、10（1分）】 10. 存放在磁盘，磁带上的文件，即可以是顺序文件，也可以是索引结构或其他结构类型的文件。 【山东大学 2001 一、7 (1分)】 11. 检索出文件中的关键码值落在某个连续的范围内的全部记录，这种操作称为范围检索。对经常需要做范围检索的文件进行组织，采用散列法优于顺序检索法。【中山大学 1994 一、 第一章绪论 一、选择题 1.组成数据的基本单位是（） （A）数据项（B）数据类型（C）数据元素（D）数据变量 2.数据结构是研究数据的（）以及它们之间的相互关系。 （A）理想结构，物理结构（B）理想结构，抽象结构 （C）物理结构，逻辑结构（D）抽象结构，逻辑结构 3.在数据结构中，从逻辑上可以把数据结构分成（） （A）动态结构和静态结构（B）紧凑结构和非紧凑结构 （C）线性结构和非线性结构（D）内部结构和外部结构 4.数据结构是一门研究非数值计算的程序设计问题中计算机的（①）以及它们之间的（②）和运算等的学科。 ① （A）数据元素（B）计算方法（C）逻辑存储（D）数据映像 ② （A）结构（B）关系（C）运算（D）算法 5.算法分析的目的是（）。 （A）找出数据结构的合理性（B）研究算法中的输入和输出的关系 （C）分析算法的效率以求改进（D）分析算法的易懂性和文档性 6.计算机算法指的是（①）,它必须具备输入、输出和（②）等5 个特性。 ① （A）计算方法（B）排序方法（C）解决问题的有限运算序列（D）调度方法 ② （A）可执行性、可移植性和可扩充性（B）可行性、确定性和有穷性 （C）确定性、有穷性和稳定性（D）易读性、稳定性和安全性 二、判断题 1.数据的机内表示称为数据的存储结构。（） 2.算法就是程序。（） 3.数据元素是数据的最小单位。（） 4.算法的五个特性为：有穷性、输入、输出、完成性和确定性。（） 5.算法的时间复杂度取决于问题的规模和待处理数据的初态。（） 三、填空题 1.数据逻辑结构包括________、________、_________ 和_________四种类型,其中树形结构和图形结构合称为_____。 2.在线性结构中,第一个结点____前驱结点,其余每个结点有且只有______个前驱结点；最后一个结点______后续结点,其余每个结点有且只有_______个后续结点。 3.在树形结构中,树根结点没有_______结点,其余每个结点有且只 有_______个前驱结点；叶子结点没有________结点,其余每个结点的后续结点可以_________。 4.在图形结构中,每个结点的前驱结点数和后续结点数可以 _________。 5.线性结构中元素之间存在________关系,树形结构中元素之间存 在______关系,图形结构中元素之间存在_______关系。 6.算法的五个重要特性是_______、_______、______、_______、 一、选择题。(每小题2分，共40分) (1) 计算机识别.存储和加工处理的对象被统称为____A____。 A.数据 B.数据元素 C.数据结构 D.数据类型 (2) 数据结构通常是研究数据的____ A _____及它们之间的联系。 A.存储和逻辑结构 B.存储和抽象 C.理想和抽象 D.理想与逻辑 (3) 不是数据的逻辑结构是____ A ______。 A.散列结构 B.线性结构 C.树结构 D.图结构 (4) 数据结构被形式地定义为 一、单项选择题 1 某算法的时间复杂度是O(n 2 ) ，表明该算法（）。 A 问题规模是n2 B 问题规模与n2成正比 C 执行时间等于n2 D 执行时间与n2成正比 2、关于数据结构的描述，不正确的是（）。 A数据结构相同，对应的存储结构也相同。 B数据结构涉及数据的逻辑结构、存储结构和施加其上的操作等三个方面。 C数据结构操作的实现与存储结构有关。 D定义逻辑结构时可不考虑存储结构。 3、按排序策略分来，起泡排序属于（）。 A插入排序B选择排序C交换排序D归并排序 4、利用双向链表作线性表的存储结构的优点是（）。 A便于进行插入和删除的操作 B 提高按关系查找数据元素的速度 C节省空间D便于销毁结构释放空间 5、一个队列的进队顺序为1,2,3,4，则该队列可能的输出序列是（）。 A 1,2,3,4 B 1,3,2,4 C 1,4,2,3 D 4,3,2,1 6、 Dijkstra算法是按（）方法求出图中从某顶点到其余顶点最短路径的。 A按长度递减的顺序求出图的某顶点到其余顶点的最短路径 B按长度递增的顺序求出图的某顶点到其余顶点的最短路径 C通过深度优先遍历求出图中从某顶点到其余顶点的所有路径 D通过广度优先遍历求出图的某顶点到其余顶点的最短路径 7、字符串可定义为n（ n≥ 0）个字符的有限（）。其中，n是字符串的长度，表明字符串中字符的个数。 A集合B数列C序列D聚合 8、在二维数组A[9][10]中，每个数组元素占用 3 个存储单元，从首地址SA 开始按行连续存放。在这种情况下，元素A[8][5]的起始地址为（）。 A SA+141 B SA+144 C SA+222 D SA+255 9、已知广义表为L(A(u,v,(x,y),z),C(m,(),(k,l,n),(())),((())),(e,(f,g),h))，则它的长度是（）。 A2B3C4D5 10.对于具有n(n>1)个顶点的强连通图，其有向边条数至少有_____。 A. n+1 B. n C. n-1 D. n-2 11.一个递归算法必须包括 __________ 。 A. 递归部分 B . 结束条件和递归部分 C. 迭代部分 D. 结束条件和迭代部分 12.从逻辑上看可以把数据结构分为__________两大类。 A．动态结构、静态结构B．顺序结构、链式结构 C．线性结构、非线性结构D．初等结构、构造型结构 13、若在长度为n 的顺序表的表尾插入一个新元素的渐进时间复杂度为（）。 A O(n) B O(1) C O(n 2) D O(log 2n) 14.采用顺序搜素方式搜索长度为 n 的线性表时，在等概率情况下，搜索成功时的平均搜索 长度为 __________。 A. n B. n/2 C . (n+1)/2 D. (n-1)/2 15、非空的循环单链表first的链尾结点（由p 所指向）满足（）。 A p->link==NULL; B P==NULL; 第 1 章绪论 课后习题讲解 1. 填空 ⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。 【解答】集合，线性结构，树结构，图结构 ⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺在一般情况下，一个算法的时间复杂度是（）的函数。 【解答】问题规模 ⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。 第1章绪论 一、判断题 1.数据的逻辑结构与数据元素本身的容和形式无关。（√） 2.一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。（√） 3.数据元素是数据的最小单位。（×） 4.数据的逻辑结构和数据的存储结构是相同的。（×） 5.程序和算法原则上没有区别，所以在讨论数据结构时可以通用。（×） 6.从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。（√） 7.数据的存储结构是数据的逻辑结构的存储映象。（√） 8.数据的物理结构是指数据在计算机实际的存储形式。（√） 9.数据的逻辑结构是依赖于计算机的。（×） 10.算法是对解题方法和步骤的描述。（√） 二、填空题 1.数据有逻辑结构和存储结构两种结构。 2.数据逻辑结构除了集合以外，还包括线性结构、树形结构和图形结构。 3.数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构。 4.树形结构和图形结构合称为非线性结构。 5.在树形结构中，除了树根结点以外，其余每个结点只有1个前驱结点。 6.在图形结构中，每个结点的前驱结点数和后继结点数可以任意多个。 7.数据的存储结构又叫物理结构。 8.数据的存储结构形式包括顺序存储、链式存储、索引存储和散列存储。 9.线性结构中的元素之间存在一对一的关系。 10.树形结构中的元素之间存在一对多的关系。 11.图形结构的元素之间存在多对多的关系。 12.数据结构主要研究数据的逻辑结构、存储结构和算法（或运算）3个方面的容。 13.数据结构被定义为（D，R），其中D是数据的有限集合，R是D上的关系有限集合。 14.算法是一个有穷指令的集合。 15.算法效率的度量可以分为事先估算法和事后统计法。 16.一个算法的时间复杂度是算法输入规模的函数。 17.算法的空间复杂度是指该算法所耗费的存储空间，它是该算法求解问题规模的n的函数。 18.若一个算法中的语句频度之和为T(n)=6n+3nlog2n,则算法的时间复杂度为O（nlog2n）。 19.若一个算法的语句频度之和为T(n)=3n+nlog2+n2,则算法的时间复杂度为O（n2）。 20.数据结构是一门研究非数值计算的程序问题中计算机的操作对象，以及它们之间的关系和运算的学 科。 三、选择题 1.数据结构通常是研究数据的（A）及它们之间的相互关系。 A．存储结构和逻辑结构B．存储和抽象C．联系和抽象D．联系与逻辑 2.在逻辑上可以把数据结构分成（C）。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．部结构和外部结构。 3.数据在计算机存储表示时，物理地址和逻辑地址相同并且是连续的，称之为（C）。 A．存储结构B．逻辑结构C．顺序存储结构D．链式存储结构 4.非线性结构中的每个结点（D）。 A．无直接前驱结点．B．无直接后继结点． 第1章概论 1.数据、数据元素、数据结构、数据类型的含义分别是什么？ 数据：对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并由计算机程序处理的符号的总称。 数据元素：数据的基本单位，在计算机程序中通常作为一个整体考虑。 数据结构：数据元素之间的关系+运算，是以数据为成员的结构，是带结构的数据元素的集合，数据元素之间存在着一种或多种特定的关系。 数据类型：数据类型是用来区分不同的数据；由于数据在存储时所需要的容量各不相同，不同的数据就必须要分配不同大小的内存空间来存储，所有就要将数据划分成不同的数据类型。数据类型包含取值范围和基本运算等概念。 2.什么是数据的逻辑结构？什么是数据的物理结构？数据的逻辑结构与物理结构的区别和联系是什么？ 逻辑结构：数据的逻辑结构定义了数据结构中数据元素之间的相互逻辑关系。数据的逻辑结构包含下面两个方面的信息： ①数据元素的信息； ②各数据元素之间的关系。 物理结构：也叫储存结构，是指逻辑结构的存储表示，即数据的逻辑结构在计算机存储空间中的存放形式，包括结点的数据和结点间关系的存储表示。 数据的逻辑结构和存储结构是密不可分的，一个操作算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采与的存储结构。采用不同的存储结构，其数据处理的效率是不同的。因此，在进行数据处理时，针对不同问题，选择合理的逻辑结构和存储结构非常重要。 3.数据结构的主要操作包括哪些？ 对于各种数据结构而言，他们在基本操作上是相似的，最常用的操作有： ●创建：建立一个数据结构； ●清除：清除一个数据结构； ●插入：在数据结构中增加新的结点； ●删除：把指定的结点从数据结构中删除； ●访问：对数据结构中的结点进行访问； ●更新：改变指定结点的值或改变指定的某些结点之间的关系； ●查找：在数据结构中查找满足一定条件的结点； ●排序：对数据结构中各个结点按指定数据项的值，以升序或降序重新排列。 4.什么是抽象数据类型？如何定义抽象数据类型？ 抽象数据类型（Abstract Data Type 简称ADT）是指一个数学模型以及定义在此数学模型上的一组操作。ADT是与具体的物理存储无关的数据类型，因此，不论ADT的内部结构如何变化，只要其数据结构的特性不变，都不影响其外部使用。 对抽象数据类型的描述一般用（D,R,P)三元组表示，抽象数据类型的定义格式为： ADT<抽象数据类型名> { 数据对象D：<数据对象的定义> 数据关系R：<数据关系的定义> 基本操作P：<基本操作的定义>数据结构标准答案
严蔚敏版数据结构课后习题答案-完整版
数据结构-第六章-图-练习题及答案详细解析(精华版)
数据结构试题库答案
数据结构c语言版试题大全含答案
数据结构习题及参考答案
数据结构复习题附答案
《数据结构》题库及答案
数据结构 习题答案
数据结构 第六章 图 练习题及答案详细解析
数据结构试题及答案(10套最新)
数据结构习题及答案-第11章 文件
数据结构习题及答案——严蔚敏
数据结构复习题及答案(12级).
算法与数据结构题库与答案
数据结构习题与答案
数据结构练习试题和答案解析
数据结构习题参考答案
- 数据结构练习试题(含答案解析)
- 数据结构复习题及答案(12级).
- 数据结构练习题(含答案)(DOC)
- 数据结构练习题及参考答案
- 数据结构 期末考试复习题及答案
- 数据结构复习题及参考答案讲诉
- 数据结构复习题及答案
- 数据结构练习题与答案
- 数据结构与算法复习题含答案
- 数据结构练习题(含答案)
- 数据结构 第六章 图 练习题及答案详细解析
- (完整版)数据结构练习题及参考答案
- 数据结构练习题(含答案)
- 数据结构各章自测题及答案
- 数据结构练习题--2011级--参考答案
- 数据结构(java)复习题及答案
- 数据结构期末复习题及部分答案解析
- 数据结构练习题及参考答案
- 数据结构复习题及答案
- 数据结构练习试题和答案解析