数据结构复习答案
一、选择填空
1.下面关于线性表的叙述中，错误的是哪一个？（    ）
  A）线性表采用顺序存储，必须占用一片连续的存储单元。
　　√B）线性表采用顺序存储，便于进行插入和删除操作。
  C）线性表采用链接存储，不必占用一片连续的存储单元。
  D）线性表采用链接存储，便于插入和删除操作。
2.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（    ）存储方式最节省时间。
√A）顺序表      B）双链表        C）带头结点的双循环链表    D）单循环链表
3.链表不具有的特点是（    ）。
A）插入、删除不需要移动元素           √B）可随机访问任一元素 
C）不必事先估计存储空间              D）所需空间与线性长度成正比
4.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（    ）(1<=i<=n+1)。
  A） O(0)          B） O(1)        √C） O(n)          D） O(n2)
5.线性表（ a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂度为（    ）。
A）O(i)          B）O(1)      √C）O(n)        D）O(i-1)
6.对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（    ）
A）head==NULL  B）head→next==NULL    √C）head→next==head  D）head!=NULL
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;
8.设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为(    )。
    √A）p->next=p->next->next            B） p=p->next   
    C）p=p->next->next                D） p->next=p
9. (    )又称为FIFO表；(    )又称为FILO表。
√A）队列        B）散列表        √C）栈        D）哈希表
10.对于栈操作数据的原则是（  ）。
A） 先进先出   √B） 后进先出    C） 后进后出    D） 不分顺序
11.用不带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向队尾结点，则在进行删除操作时(    )。
√A）仅修改队头指针                      B） 仅修改队尾指针 
C） 队头、队尾指针都要修改          D） 队头、队尾指针都可能要修改
12.假设以数组A[m]存放循环队列的元素，其头尾指针分别为front和rear，则当前队列中的元素个数为（    ）。
  √A）(rear-front+m)%m    B）rear-front+1      C）(front-rear+m)%m      D）(rear-front)%m
13.栈和队列的共同点是（    ）。
A） 都是先进先出                          B） 都是先进后出 
√C） 只允许在端点处插入和删除元素          D） 没有共同点
14.设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是(    )。
  A） 6          B） 4          √C） 3          D） 2
15.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（    ）。
  A） 12                  √B） 33              C） 18              D） 40
16.由3 个结点可以构造出多少种不同的二叉树？(    )
  A）2          B）3            C）4            √D）5
17.二叉树中第i(i≥1)层上的结点数最多有(    )个。
    A） 2i        B） 2i        √C） 2i-1        D） 2i-1
18.在有n个叶子结点的哈夫曼树中，其结点总数为(    )。
A）不确定  B）2n    C）2n+1      √D）2n-1 
19.一棵二叉树高度为h，所有结点的度或为0、或为2，则这棵二叉树最少有(    )结点。
A）2h            √B）2h-1                C）2h+1            D）h+1
20.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是(    )。
A）9                    √B）11                C）15              D）不确定
21.树的后根遍历序列等同于该树对应的二叉树的(    )。
A） 先序序列                  √B） 中序序列            C） 后序序列        D）层序序列
22.在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序(    )。
A）都不相同                              √B）完全相同 
C）先序和中序相同，而与后序不同　        D）中序和后序相同，而与先序不同
23.下列哪一种图的邻接矩阵是对称矩阵？(    )
  A）有向图           √B）无向图              C）AOV网          先序中序后序遍历二叉树    D）AOE网
24.在一个无向图中，所有顶点的度数之和等于所有边数(  2  )倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的(  1  )倍。
  A）1/2                  √B）2                    √C）1                  D）4
25.一个有n个顶点的无向图最多有(    )条边。由n个顶点组成的有向图，最多可以有(    )条边。
A）n*n        B）2n        √C）n(n-1)        √D）n(n-1)/2
26.下列说法不正确的是(    )。
A）图的遍历是从给定的源点出发每一个顶点仅被访问一次 
B）遍历的基本算法有两种：深度遍历和广度遍历 
√C）图的深度遍历不适用于有向图 
D）图的深度遍历是一个递归过程
27.下面哪一方法可以判断出一个有向图是否有环(回路) (    )。
  A）深度优先遍历      √B） 拓扑排序      C） 求最短路径      D） 求关键路径 
28.下列算法中，(    )算法用来求图中每对顶点之间的最短路径。
A）Dijkstra        √B）Floyed        C）Prim        D）Kruskal
29.关键路径是事件结点网络中(    )。
  √A）从源点到汇点的最长路径        B）从源点到汇点的最短路径
  C）最长回路                            D）最短回路
30.若查每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查法查一个记录，其平均查长度ASL为(    )。
  A） (n-1)/2              B） n/2                √C） (n+1)/2                D） n
31.下面关于二分查的叙述正确的是  (    ) 。
A） 表必须有序，表可以顺序方式存储，也可以链表方式存储 
B） 表必须有序，而且只能从小到大排列　
C 表必须有序且表中数据必须是整型，实型或字符型 
√D） 表必须有序，且表只能以顺序方式存储
32.折半查的时间复杂性为(  ) 。
  A） O(n2)                B） O(n)            C） O(nlogn)            √D） O(logn)
33.当采用分快查时，数据的组织方式为  (    ) 。
  A）数据分成若干块，每块内数据有序
  √B）数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块
  C） 数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引块
  D） 数据分成若干块，每块(除最后一块外)中数据个数需相同 
34.下面关于哈希(Hash，杂凑)查的说法正确的是(    )。
  A）哈希函数构造的越复杂越好，因为这样随机性好，冲突小
  B）除留余数法是所有哈希函数中最好的
  √C）不存在特别好与坏的哈希函数，要视情况而定
  D）若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可
35.下面给出的四种排序法中(    )排序法是不稳定性排序法。
  A） 插入          B） 冒泡              C） 二路归并       √D） 堆
36.稳定的排序方法是(    ) 。
A）直接插入排序和快速排序        √B）折半插入排序和起泡排序 
C）简单选择排序和四路归并排序    D）树形选择排序和shell排序
37.有一组数据(15，9，7，8，20，-1，7，4) 用快速排序的划分方法进行一趟划分后数据的
排序为 (    )(按递增序)。
  √A）下面的B，C，D都不对。            B）9，7，8，4，-1，7，15，20
  C）20，15，8，9，7，-1，4，7        D）9，4，7，8，7，-1，15，20
38.设有一个文件有200个记录，按分块查法查记录，如分成10块，每块20个记录，用二分查法查索引表，用顺序查法查块内记录，则平均查长度为(    )。
A）8）4            B）10）5            C）13）4            √D）16
39.快速排序在最坏情况下的时间复杂性为(    )。
A）O(nlog2n)        √B）O(n2)        C）O(n)        D）O(nlogn)
二、填空
1.一个算法的效率可分为 时间  效率和    空间    效率。
2.线性表L=（a1,a2,…,an）用数组表示，假定插入、删除表中任一元素的概率相同，则插入
、删除一个元素平均需要移动元素的个数是  n/2            和    (n-1)/2    。
3.对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为    O(1) ，在给定值为x的结点后插入一个新结点的时间复杂度为  O(n)  。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。