第1-3章 相关习题
一、选择题
1.若进栈序列为a,b,黄冈师范学院学报c,d,进栈过程中可以出栈,则 不可能是一个出栈序列。
A) a,d,c,b B) b,c,d,a C) c,a,d,b D) c,d,b,a天水师院选课系统
6.设用一维数组A[1,…,n]来存储一个栈,令A[n]为栈底,用整型变量T指示当前栈顶位置,A[T]为栈顶元素。当从栈中弹出一个元素时,变量T将变化为 。 A) T=T + 1 B) T=T – 1 C) T不变 D) T= n
7. 一个栈的入栈序列为a,b,c,d,e,则栈不可能的出栈序列是 。
A) e d c b a B) d e c b a C) d c e a b D) a b c d e
8.若语句S的执行时间为O(1),那么下列程序段的时间复杂度为 。
For(i = 0; i <= n ; i++)
For(j = 0; j <=n ;j++)
s
A) O(n) B) O(n*n) C) O(n*log2n) D) O(n*i)
18.设计一个判断表达式中左右括号是否配对的算法,采用 数据结构最佳。 A) 队列 B) 堆栈 C) 二叉树 D) 链表
24.一个队列的入队序列是1,2,3,4,则队列的输出序列是 。
A) 1,4,3,2 B) 4,3,2,1 C) 1,2,3,4 D) 3,2,4,1
29.在一个单链表中,若要删除P结点的后续结点,则应执行 。
A) P->next = P->next->next B) p = P->next; P->next = P->next->next C) delete(P->next) D) p = P->next->next
30.在计算递归函数时,如不使用递归过程,则一般情况下必须借助于 数据结构。
A) 栈 B) 树 C) 双向队列 D) 广义表
41.下列叙述中,正确的是 。
A) 用指针的方式存储一棵有n个结点的二叉树最少需要n+1个指针
安徽大学
B) 不使用递归,也可以实现二叉树的前序、中序和后序遍历
C) 已知树的前序遍历并不能唯一确定一棵树,因为不知道树的根结点是哪一个
D) 任一棵树的平均查时间都小于用顺序查法查同样结点的线性表的平均查时间 50.以下有关数据结构的叙述,正确的是 。
A) 线性表的线性存储结构优于链式存储结构 B) 二叉树的第i层上有2i-1个结点,深度为k的二叉树上有2k-1个结点
C) 二维数组是其数据元素为线性表的线性表 D) 栈的操作方式是先进先出
52.在一个单链表中,若要在指针P所指向的结点之后插入结点q,应执行的操作是 。 A) P->next=q B) P->next=q; q->next=P->next->next C) q->next = P->next; P->next:=q D)P->next=q; q->next=P->next
56.若进栈序列为3,5,7,9,进栈过程中可以出栈,则 不可能是一个出栈序列。
A) 7,5,3,9 B) 9,5,7,3 C) 9,7,5,3 D) 7,5,9,3
57.设栈S和队列Q的初始状态为空,元素e1,e2,e3,e4,e5,e6依次通过栈,一个元素出栈后立即进入队列Q,若6个元素出队的顺序是e2,e4,e3,e6,e5,e1,则栈S的容量至少应该是 。
A) 4 B) 6 C) 3 D) 2
59.有6个元素按6,5,4,3,2,1的顺序进栈,以下序列中,不合法的出栈序列是 。
A) 3,4,6,5,2,1 B) 5,4,3,6,1,2 C) 2,3,1,4,5,6 D) 4,5,3,1,2,6
61.下面关于线性表的叙述中,错误的是 。
A) 线性表采用顺序存储,必须占用一片连续的存储单元 B) 线性表采用顺序存储,便于进行插入和删除操作
C) 线性表采用链式存储,不必占用一片连续的存储单元 D) 线性表采用链式存储,便于插入和删除操作。
62.下述 是顺序存储方式的优点。
A) 存储密度大 B) 插入运算方便 C) 删除运算方便 D) 可方便地用于各种逻辑结构的存储表示
64.向顺序栈中压入元素时,是 。
A) 先移动栈顶指针,后存入元素 B) 先存入元素,后移动栈顶指针 C) 谁先谁后无关紧要 D) 同时进行
65.在一个顺序存储的循环队列中,队首指针指向队首元素的 。
A) 前一个位置 B) 后一个位置 C) 队首元素位置 D) 任意位置
67.栈和队列都是 。
微型空调A) 限制存取点的线性结构 B) 限制存取点的非线性结构 C) 顺序存储的线性结构 D) 链式存储的线性结构
68.用链表表示线性表的优点是 。
A) 便于随机存储 B) 花费的存储空间较顺序存储少 C) 便于插入和删除操作 D) 数据元素的物理顺序与逻辑顺序相同
69在一个具有n个单元的顺序栈中,假设以地址高端作为栈顶,以top作为栈顶指针,则当做退栈处理时,top的变化为 。
A) top不变 B) top = 0 C) top = top - 1 D) top = top + 1
72.以下 不是队列的基本运算。
A) 从队尾插入一个新元素 B) 从队列中删除第i个元素 C) 判断一个队列是否为空 D) 读取队头元素的值
74.在长度为n的顺序表中,向第i个元素(1 <= I <= n+1)之前插入一个新元素时,需向后移
动 个元素。
A) n - i B) n – i + 1 C) n – i - 1 D) i
80.对于一个线性表,若即要求能够进行较快的插入和删除,又要求存储结构能够反映数据元素之间的逻辑关系,则应该 。
A) 以顺序方式存储 B) 以链接方式存储 C) 以散列方式存储 D) 可以上面任意一种方式存储
85.在数据结构中,从逻辑上可以把数据结构分为 。
A) 紧凑结构和非紧凑结构 B) 动态机构和静态结构 C) 内部结构和外部结构 D) 线性结构和非线性结构
87. 一维数组与线性表的区别是 。
A) 后者长度固定,前者长度可变 B) 两者长度均可变 C) 前者长度固定,后者长度可变 D) 两者长度均固定
108.下列有关数据的存储结构的叙述中,正确的是 。
A) 数据存储方式的优点是存储密度大,且插入和删除运算效率高 B) 链表的每个结点都恰好包含一个指针
C) 邻接表法只能用于有向图的存储,而相邻矩阵法对于有(无)向图的存储都适用
D) 队列的存储方式既可以是顺序方式,也可以是链接方式
二、填空题
4.设有二维数组A[0…9, 0…19],其每个元素占两个字节,数组按列优先顺序存储,第一个元素的存储地址为100。那么元素a[6,6]的存储地址为 。
7.在计算递归函数时,如果不用递归过程,则应借助于 数据结构。
8.在一个链队中,如果FRONT 和REAR分别表示队首和队尾指针,则插入一个结点S↑的操作是 。
11.从一个长度为N的顺序表中删除第I(1 <= I <= N)个元素,需要向前移动 个元素。
12.数据结构包括的3个方面的内容是:数据的 、数据存储结构和数据的运算。
13.单链表是 的链式存储表示。链栈和链队分别是 和 的链式存储表示。
14.在具有N个单元、顺序存储的循环队列中,队满时共有 个元素。
15.数据结构即数据的逻辑结构包括 、 、和 3种类型,数据的存储结构即物理结构包括 、 、 和 4种基本类型。
自摆乌龙
17. 是这样一种线性表,即所有插入和删除操作都在表的两端进行。
第4章 数组 习题
11.二维数组M[I,j]的元素是4个字符(每个字符占一个存储单元)组成的串,行下标i的范围从0到九宫算4,列下标j的范围从0到5。M按行存储时元素M[3,5]的起始地址与M按列存储时元素 的起始地址相同。
A) M[2,4] B) M[3,4] C) M[3,5] D) M[4,4]
二、填空题
9.对于一个二维数组,1..n],若按列为主序存储,则任意一个元素A[I,i]的相对地址是 。
第7章查相关习题
17.有m个结点的霍夫曼树,其结点的个数为 。
A) 2m B) 2m+1 C) 2m-1 D) 2(m+1)
23.二分查法适用于存储结构为 的、按关键字排好序的线性表。
A) 顺序存储或链式存储 B) 顺序存储 C) 索引存储 D) 链式存储
31.一个序列中有若干个元素,若只想得到其中1个元素之前的部分排序,最好采用 排序。
A) 堆排序 B) 插入排序 C) shell排序 D) 快速排序
32.下列有关查与排序的说法中正确的是 。
A) 堆排序所需的时间与待排序的记录个数无关 B) 如果某种排序算法是不稳定的,则该方法没有实际应用价值