《数据结构与算法》
一、选择题
1. 组成数据的基本单位是( )。
(A) 数据项 (B)数据类型 (C)数据元素 (D)数据变量
2. 线性表的链接实现有利于( )运算。
(A) 插入 (B)读表元 (C)查 (D)定位
3. 串的逻辑结构与( )的逻辑结构不同。
完全二叉树算法(A) 线性表 (B)栈 (C)队列 (D)树
4. 二叉树第i（i≥1）层最多有( )个结点。
(A) 2i (B)2i (C) 2i-1 (D) 2i-1
5. 设单链表中指针p指向结点A，若要删除A后结点（若存在），则需要修改指针的操
作为( )
(A) p->next = p->next->next (B)p=p->next
(C)p=p->next->next (D)p->next=p
6、栈和队列的共同特点是( )。
(A)只允许在端点处插入和删除元素 (B)都是先进后出
(C)都是先进先出 (D)没有共同点
7、二叉树的第k层的结点数最多为( ).
(A)2k+1 (B)2K+1 (C)2K-1(D) 2k-1
8、设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（）。
(A) BADC (B) BCDA (C) CDAB (D) CBDA
9、设某完全无向图中有n个顶点，则该完全无向图中有（）条边。
(A) n(n-1)/2 (B) n(n-1) (C) n2 (D) n2-1
10、下面程序的时间复杂为（）
for（i=1,s=0; i<=n; i++）
{t=1;
for(j=1;j<=i;j++)
t=t*j;
s=s+t;}
(A) O(n) (B) O(n2) (C) O(nlog2n) (D) O(n3)
11、设某强连通图中有n个顶点，则该强连通图中至少有（）条边。
(A) n(n-1) (B) n+1 (C) n (D) n(n+1)
12、设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（）条有向边。
(A) n (B) n-1 (C) m (D) m-1
13、i层（i≥1）二叉树最多有( )个结点。
(A) 2i (B)2i (C) 2i-1 (D) 2i-1
14、对稀疏矩阵进行压缩存储目的是( )。
A．便于进行矩阵运算 B．便于输入和输出
C．节省存储空间 D．降低运算的时间复杂度
15、数据结构是研究数据的( )以及它们之间的相互关系。
(A) 理想结构、物理结构 (B) 理想结构、抽象结构
(C) 物理结构、逻辑结构 (D) 抽象结构、逻辑结构
16、线性表采用链式存储时，其地址( )。
(A) 必须是连续的 (B) 部分地址必须是连续的
(C) 一定是不连续的 (D) 连续与否均可以
17、设循环队列N-1]的头尾指针为F，R，当插入元素时尾指针R加1，头指针F总是指向队列中第一个元素的前一个位置，则队列中元素计数为( )。
(A) R-F (B) N-(R-F) (C) (R-F+N)%N (D) (F-R+N)%N
18、链表不具有的特点是( )。
(A)插入、删除不需要移动元素 (B)可随机访问任一元素
(C)不必事先估计存储空间 (D)所需空间与线性长度成正比
19、设一数列的输入顺序为1,2,3,4,5,6，通过栈操作不可能排成的输出序列为( )
(A) 3,2,5,6,4,1 (B) 1,5,4,6,2,3
(C) 2,4,3,5,1,6 (D) 4,5,3,6,2,1
20、一个5×5的对称矩阵采用压缩存储，需要存储（）个元素。
(A)5 (B)10 (C)15 (D)20
21、判定一个栈ST（最多元素为MaxSize）栈满的条件是( )。
(A)ST->top!=1 (B)ST->top= =1
(C)ST->top!=MaxSize-1 (D)ST->top= =MaxSize-1
22、设有序顺序表中有n个数据元素，则利用二分查法查数据元素X的平均查长度为（）。
(A) log2n+1 (B) log2n-1 (C) log2n (D) log2(n+1)
23、从一个长度为n的顺序表中删除第i个元素（1≤i≤n），需向前移动( )个元素。
(A) n-i (B) n-i+1 (C) n-i-1 (D) i
24、函数substr(“DATASTRUCTURE”，5，9)的返回值为（）。
(A) “STRUCTURE”(B) “DATA”
(C) “ASTRUCTUR” (D) “DATASTRUCTURE”
25、设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发可以得到一种深度优先遍历的顶点序列为（）。
(A) abedfc (B) acfebd (C) aebdfc (D) aedfcb
26、3个结点可构成（）个不同形态的二叉树。
(A)2 (B)3 (C)4 (D)5
27、下列哪一种图的邻接矩阵是对称矩阵？（）
(A)有向图 (B)无向图 (C)AOV网 (D)AOE网
28、（）二叉排序树可以得到一个从小到大的有序序列。
(A) 先序遍历(B) 中序遍历 (C) 后序遍历(D) 层次遍历
29、若给定关键字集合为{20,15,14,18,21,36,40,10}，一趟快速排序结束时，键值的排列为( )
(A) 10,15,14,18,20,36,40,21 (B) 10,15,14,18,20,40,36,21
(C) 10,15,14,20,18,40,36,21 (D) 15,10,14,18,20,36,40,21
30、对于含有n个顶点e条边的无向连通图，利用Prim算法生成最小代价生成树其时间复杂度为( )，利用Kruskal的时间复杂度为( )。
(A) O(log
2n) (B) O(n2) (C) O(ne) (D) O(elog
2
e)
31、具有n个顶点的完全有向图的边数为( )。
(A) n(n-1)/2 (B) n(n-1) (C) n2 (D) n2-1
32、树最适合用来表示( )。
(A)有序数据元素 (B)无序数据元素
(C)元素之间具有分支层次关系的数据 (D)元素之间无联系的数据
33、具有2000个结点的二叉树，其高度至少为( )。
(A) 9 (B) 10 (C) 11 (D) 12
34、设有1000个元素，用二分法查时，最小比较次数为( )。
(A)0 (B)1 (C)10 (D)500
35、栈操作的原则是( )
（A）先进先出（B）后进先出（C）栈顶插入（D）栈顶删除
36、一个栈的入栈序列是１，２，３，则栈的输出序列有（）种
(A)3 (B)2 (C)5 (D)4
37、当利用大小为N的一维数组顺序存储一个栈时，假定用top=－1表示栈空，则向这个栈插入一个元素时，首先应执行（）语句修改top指针。
(A)top++ (B)top-- (C)top=NULL (D)top
38、线性表采用顺序存储时，结点的存储地址（）
（A）必须是不连续的（B）连续与否均可
（C）必须是连续的（D）和头结点的存储地址有关
39、已知完全二叉树有26个结点，则整棵二叉树有多少个度为1的结点？（）
（A）1 （B）0 （C）2 （D）不确定
40、在一个具有n个结点的单链表中查其值等于x的结点，在查成功的情况下，需平均比较( )个元素结点。
(A) n/2 (B) n (C) (n+1)/2 (D) (n-1)/2
41、串的长度是( )。
(A) 串中不同字符的个数 (B) 串中不同字母的个数
(C) 串中所含字符的个数n(n>0) (D) 串中所含字符的个数n(n≥0)
42、若有一个栈的输入序列是1,2,3,…,n，输出序列的第一个元素是n，则第i个输出元素是( )
(A) n-i (B) n-i-1 (C) n-i+1 (D) 不确定
43、设有一个栈，元素的进栈次序A，B，C，D，E，下列( )是不可能的出栈序列。
(A) A,B,C,D,E （B）B,C,D,E,A
(C) E,A,B,C,D （D）E,D,C,B,A
44、具有20个结点的二叉树，其深度最多为。
(A)4 (B)5 (C)6 (D)20
45、在一个具有n个结点的无向完全图中，包含有( )条边。
(A) n(n-1)/2 (B) n(n-1) (C) n(n+1)/2 (D) n2
46、采用顺序检索的方法检索长度为n的线性表，则检索每个元素的平均比较次数为( )。(A) n (B) n/2 (C) (n+1)/2 (D)
(n-1)/2
47、二维数组A[4][5]按行优先顺序存储，若每个元素占2个存储单元，且第一个元素A[0][0]的存储地址为1000，则数组元素A[3][2]的存储地址为（）
(A) 1012 (B) 1017 (C) 1034 (D) 1036
48、已给下图，哪一项是该图的拓扑排序？（）
(A)a，b，c，d，e (B)a，c，b，d，e
(C)a，b，d，c，e (D)a，b，c，e，d
49、下面程序段的时间复杂度为（）。
for(i=0;i<m;i++)
for(j=0;j<n;j++)
A[i][j]=i*j;
（A）O(m2) （B）O(n2)
（C）O(m+n) （D）O(m*n)
50、在一个单链表中，已知*q结点是*p结点的前趋结点，若在*q和*p之间插入*s结点，则需执行（）。
（A）s->next=p->next; p->next=s; （B）q->next=s; s->next=p;
（C）p->next=s->next; s->next=p; （D）p->next=s; s->next=q;
51、设一组初始记录关键字序列为(45，80，55，40，42，85)，则以第一个记录关键字45
为基准而得到一趟快速排序的结果是（）。
(A) 40，42，45，55，80，83 (B) 42，40，45，80，85，88
(C) 42，40，45，55，80，85 (D) 42，40，45，85，55，80
52、设某哈夫曼树中有199个结点，则该哈夫曼树中有（）个叶子结点。
(A) 99 (B) 100 (C) 101 (D) 102
53、在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行。
A、p = q->next ; p->next = q->next;
B、p = q->next ; q->next = p;
C、p = q->next ; q->next = p->next;
D、q->next = q->next->next; q->next = q;
54、栈的插入与删除操作在进行。
A、栈顶
B、栈底
C、任意位置
D、指定位置
55、在一个循环顺序队列中，队首指针指向队首元素的位置。
A、前一个
B、后一个
C、当前
D、后面
56、由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为________。
A、 24
B、 48
C、 72
D、 53
57、当利用大小为N的一维数组顺序存储一个栈时，假定用top=－1表示栈空，则向这个栈
插入一个元素时，首先应执行语句修改top指针。
A．top++； B．top--； C．top=NULL ； D．top；
58、线性表L在( )情况下适合使用链式结构实现。
(A)需经常修改L中的结点值
(B)需不断对L进行删除、插入
(C)L中含有大量的结点
(D)L中结点结构复杂
59、设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（）。
(A) 第i行非0元素的个数之和(B) 第i列非0元素的个数之和
(C)第i行0元素的个数之和(D) 第i列0元素的个数之和
60、设一组初始记录关键字序列为(13，18，24，35，47，50，62，83，90，115，134)，则
利用二分法查关键字90需要比较的关键字个数为（）。
(A) 1 (B) 2 (C) 3 (D) 4
61、设在一棵度数为3的树中，度数为3的结点数有2个，度数为2的结点数有1个，度数
为1的结点数有2个，那么度数为0的结点数有（）个。
(A) 4 (B) 5 (C) 6 (D) 7
62、在内部排序中，排序时不稳定的有（）。
（A）插入排序（B）冒泡排序
（C）快速排序（D）归并排序
63、设字符串S1=‘ABCDEFG’，S2=‘PQRST’，则运算S=CONCAT(SUB(S1,2,LENGTH(S2))，SUB(S1,LENGTH(S2),2))的结果为( )
(A) ‘BCQR’ (B) ‘BCDEF’ (C) ’BCDEFG’ (D) ‘BCDEFEF’
64、在计算机存储器内表示数据时，物理地址与逻辑地址相同并且是连续的，称之为( )。
(A)存储结构(B)逻辑结构(C)顺序存储结构(D)链式存储结构
65、链接存储的存储结构所占存储空间( )。
(A)分为两部分，一部分存放结点值，另一部分存放表示结点之间关系的指针
(B)只有一部分，存放结点值
(C)只有一部分，存储表示结点之间关系的指针
(D)分为两部分，一部分存放结点值，另一部分存放结点所占单元数
66、下列排序方法中，( )是稳定的排序方法。
(A)希尔排序 (B)直接选择排序 (C)快速排序 (D)直接插入排序
67、一组记录的关键字序列为(46,79,56,38,40,84)，则利用堆排序的方法建立的初始堆为( )。
(A)79,46,56,38,40,84 (B)84,79,56,38,40,46
(C)84,79,56,46,40,38 (D)84,56,79,40,46,38
68、下列排序算法中，其中（）是稳定的。
A. 堆排序，冒泡排序
B. 快速排序，堆排序
C. 直接选择排序，归并排序
D. 归并排序，冒泡排序
69、当采用分快查时，数据的组织方式为 ( )
A．数据分成若干块，每块内数据有序
B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块
C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块
D. 数据分成若干块，每块（除最后一块外）中数据个数需相同
70、对线性表进行二分查时，要求线性表必须（）
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论