《数据结构与算法》学期考试复习题2015-2016
学年第1
该版纠错题有：7,16,22
一、 选择题（下面各小题有一个正确答案，请将正确答案的编号填写在各小题的括号内）。
1、在一棵具有5层的满二叉树中结点总数为（ A ）。
A) 31 B）32 C）33 D）16
2、串的逻辑结构与（ D ）的逻辑结构不相同。
A）线性表 B）栈 C）队列 D）集合
3、下列序列中，执行第一趟快速排序后得到的序列是（ A ）。
A）[d,a,e,d,b]f[h,g] B) [c,e,a,d]f[h,g,b] C) [g,a,e,c,b]f[d,h] D) [a,b,c,d,]f[e,g,h] 4、n个顶点的强连通图至少有（ A ）条边。
A）n B）n+1 C）n-1 D）n(n-1) 5、数据结构中，在逻辑上可以把数据结构分成（ B ）。
A）动态结构和静态结构 B）线性结构和非线性结构
C）紧凑结构和非紧凑结构 D）内部结构和外部结构
6、链式存储的存储结构所占存储空间（ A ）。
A）分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 B）只有一部分，存放结点值
C）只有一部分，存储表示结点间关系的指针
D）分两部分，一部分存放结点值，另一部分存放结点所占单元数
7、有一个有序表{1，4，6，10，18，35，42，53，67，71，78，84，92，99}。当用二分查找法查找键值为84的结点时，经（ A ）比较后查找成功。 A) 4 B)3 C)2 D)12
8、设单链表中指针p指向结点m，若要删除m之后的结点（若存在），则需修改指针的操作为（ A ）。
A）p->next=p->next->next; B） p=p->next; C）p=p->next->next; D） p->next=p;
9、n个顶点，e条边的有向图的邻接矩阵中非零元素有（ C ）个。 A）n B）2e C）e D） n+e 10、对下图V4的度为（ C ）。
A）1 B）2 C）3 D）4
v1
v2 v3
v4
11、在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为（ C ）。
A）4 B）5 C）6 D）7
12、在数据结构中，从逻辑上可以把数据结构分为（ C ）。
A）动态结构和静态结构 B）紧凑结构和非紧凑结构 C）线性结构和非线性结构 D）内部结构和外部结构
13、用一维数组A进行顺序存储时，若起始地址为loc(A1)，元素长度为c，则A的第i个数组单元在存放地址loc(Ai)，等于（ B ）。
A）loc(A1)+i*c B）loc(A1)+(i-1)*c C）loc(A1)+i*c+1 D）loc(A1)+(i+1)*c 14、（ C ）在进行插入操作时，常产生假溢出现象。
A）顺序栈 B）循环队列 C）顺序队列 D）链队列 15、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。
A) 单链表 B) 仅有头指针的单循环链表 C) 双链表 D) 仅有尾指针的单循环链表 16、向一个栈顶指针为hs的链栈中插入一个s结点时，应执行（ C ）。 A) hs->next=s; B) s->next=hs->next; hs->next=s; C) s->next=hs; hs=s; D) s->next=hs; hs=hs->next; 17、在一个链队列中，假定front和rear分别为队首和队尾指针，则删除一个结点的操作为（ B ）。
A) rear=rear->next; B) front=front->next;
C) rear=front->next; D) front=rear->next ; 18、已知栈的最大容量为4。若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行,则可能出现的出栈序列为（ C ）。
A) 5，4，3，2，1，6 B) 2，3，5，6，1，4 C) 3，2，5，4，1，6 D) 1，4，6，5，2，3
19、已知广义表L=((x,y,z),a,(u,t,w))，从L 表中取出原子项t 的操作是（ D ）。
A) Head(Head(Tail(Tail(L)))) B) Tail(Head(Head(Tail(L)))) C) Head(Tail(Head(Tail(L)))) D)Head(Tail(Head(Tail(Tail(L)))))
20、下列各种数据结构中属于线性结构的有（ A ）。 A）栈 B) 二叉树 C) 广义表 D) 图
21、倘若在对串的插入、删除运算中，期望运算速度最快，则应采用（ C ）。 A）顺序表示法 B）单字符为结点的单链表表示法 C）等量分块表示法 D）不等量分块表示法 22、广义表head(((a,b),(c,d)))的运算结果为（ D ）。 A）(a,b) B）(c,d) C）空表 D）（（a,b）,(c,d)） 23、 n个顶点的图的最小生成树必定（ D ），是不正确的描述。 A）不唯一 B）权的总和唯一 C）不含回路 D）有n条边 24、采用链结构存储线性表时，其地址（ B ）。
A）必须是连续的 B）连续不连续都可以 C）部分地址必须是连续 D）必须是不连续的 25、队列的操作的原则是（ A ）。
A）先进先出 B) 后进先出 C) 只能进行插入 D) 只能进行删除 26、以下属于顺序存储结构优点的是（ A ）。
A) 存储密度大 B) 插入运算方便
C）删除运算方便 D）可方便地用于各种逻辑结构的存储表示 27、数据结构研究的内容是（ D ）。
A）数据的逻辑结构 B）数据的存储结构 C）建立在相应逻辑结构和存储结构上的算法 D）包括以上三个方面 28、在一个单链表中，已知q结点是p结点的前趋结点，若在q和p之间插入s结点，则须执行（ A ） 。
A）q->next=s; s->next=p; B）s->next=p->next; p->next=s; C）p->next=s->next; s->next=p D）p->next=s; s->next=q; 29、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ D ）存储方式最节省时间。
A）顺序表 B）双链表 C）带头结点的双循环链表 D）单循环链表 30、下面关于线性表的叙述中，错误的是哪一个？（ D ） A）线性表采用顺序存储，必须占用一片连续的存储单元。 B）线性表采用链接存储，便于插入和删除操作。
C）线性表采用链接存储，不必占用一片连续的存储单元。 D）线性表采用顺序存储，便于进行插入和删除操作。
31、在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，
以top作为栈顶指针，当做出栈处理时，top变化为（ C ）。
A）top不变 B）top=0 C）top-- D）top++
32、在一个链队列中，假定front和rear分别为队首和队尾指针，则插入一个结点的操作为（ B ）。
A）front=front->next; B） rear=rear->next;
C） rear=front->next; D） front=rear->next ;
33、设有一个栈，元素的进栈次序为A, B, C, D, E,下列是不可能的出栈序列是（ C ）。
A） A, B, C, D, E B） B, C, D, E, A
C） E, A, B, C, D D） E, D, C, B, A 34、广义表A=（A,B,(C,D),(E,(F,G))），则head(tail(head(tail(tail(A)))))=（ D ）。
A） (G) B） (D) C） C D） D
35、设给定问题的规模为变量n，解决该问题的算法所需时间为Tn=O(f(n)),Tn表示式中记号O表示（ A ）。
A）一个数量级别 B）一个平均值 C）一个最大值 D）一个均方值 36、线性表的链接实现有利于（ A ）运算。
A）插入 B）读元素 C）查找 D）定位
37、串的逻辑结构与（ D ）的逻辑结构不同。
A）线性表 B）栈 C）队列 D）树 38、下面程序段的时间复杂度是( A )。
s =0;
for( i =0; i sum = s ; A） O(n2) B） O(n) C） O(m*n) D）O(1) 39、二叉树第i(i≥1)层上至多有（ C ）结点。 A）2i B）2i C）2i-1 D）2i-1 40、设单链表中指针p指着结点A，若要删除A之后的结点（若存在），则需要修改指针的操作为（ A ）。 A）p->next=p->next->next B）p=p->next C）p=p->nexe->next D）p->next=p 41、设一数列的顺序为1，2，3，4，5，6，通过栈结构不可能排成的顺序数列 为（ B ）。 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 42、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点的个数是( B )。 A）9 B）11 C）15 D）不能确定 43、对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是（ A ）。 A）直接选择排序 B）直接插入排序 C）快速排序 D）起泡排序 44、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一个元素，其存储地址为1，每元素占1个地址空间，则a85的地址为（ B ）。 A）13 B）33 C）18 D）40 45、如果结点A有3个兄弟，而且B为A的双亲，则B的度为（ B ）。 A）3 B）4 C）5 D）1 46、线索二叉树中某结点D，没有左孩子的条件是（ B ）。 A）D->Lchild=Null B) D->ltag=1 C) D->Rchild=Null D) D->ltag=0 47、栈进行插入和删除操作的特点是（ A ）。 A）LIFO B）FIFO C）FCFS D）HPF 48、与无向图相关的术语有（ C ）。 A）强连通图 B）入度 C）路径 D）弧 49、 n个顶点的图的最小生成树必定（ D ），是不正确的描述。 A）不唯一 B）权的总和唯一 C）不含回路 D）有n条边 50、若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个（ D ）。 A）上三角矩阵 B) 稀疏矩阵 C) 对角矩阵 D) 对称矩阵 51、采用链结构存储线性表时，其地址（ B ）。 A）必须是连续的 B）连续不连续都可以 C）部分地址必须是连续 D）必须是不连续的 52、倘若在对串的插入、删除运算中，期望运算速度最快，则应采用（ B ）。 A）顺序表示法 B）单字符为结点的单链表表示法 C）等量分块表示法 D）不等量分块表示法 53、在循环队列中，若front与rear 分别表示对头元素和队尾元素的位置，则判断循环队列空的条件是( C )。 A）front==rear+1 B）rear==front+1 C）front==rear D）front==0 二、判断题（对的打√，错的打 ╳） 1、算法和程序都应具有下面一些特征：有输入，有输出，确定性，有穷性，有效性。（ 1 ） 2、顺序表和一维数组一样，都可以按下标随机（或直接）访问。（ 1 ） 3、线性表的链式存储结构优于顺序存储。（ 0 ） 4、对稀疏矩阵进行压缩存储是为了节省存储空间。（ 1 ） 5、数据的逻辑结构反映了数据在计算机中的存储方式。（ 1 ） 6、从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较 (n+1)/2个元素结点。（ 1 ） 7、在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为：(rear+l)％n= = front。（ 1 ） 8、选择好的哈希函数就可以完全避免冲突的发生。 （ 0 ） 9、栈和队列都是顺序存取的线性表，它们对存取位置的限制是一样的。（ 0 ）10、在铁路的列车调度中，假设两侧铁道均为单向行驶道，如果进站的列车序列为123456，则一定能得到435612和135426的出站序列。（ 0 ） 11、广义表是由零个或多个原子或子表所组成的有限序列，所以广义表可能为空表。（ 0 ） 12、数组是一种复杂的数据结构，数组元素之间的关系，即不是线性的也不是树形的。（ 0 ） 13、用邻接表存储图所用的空间大小与图的顶点数和边数都有关。（ 0 ） 14、设散列表长度为m，散列函数为H（key）=key% p，为了减少发生冲突的可能性，p应取小于m的最大奇数。（ 1 ） 15、在排序前，关键字值相等的不同记录间的前后相对位置保持不变的排序方法称为稳定的排序方法。（ 1 ） 16、引入线索二叉树的目的是为了能在二叉树中方便的进行插入与删除。（ 0 ）17、算法分析的主要任务是研究数据之间的逻辑关系。（ 0 ） 18、在一个长度为n的顺序表中删除第i个元素(0?i?n)时，需向前移动n?i个元素。（ 0 ） 19、在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队空的条件为：rear= = front。（ 0 ） 20、在铁路的列车调度中，假设两侧铁道均为单向行驶道，如果进站的列车序列为123456，则只能得到654321的出站序列。（ 0 ） 21、在一棵二叉树中，假定每个结点只有左孩子，没有右孩子，对它分别进行前序遍历和中根遍历，则具有相同的结果。（ 0 ） 22、广义表((a,b),a,b)的表头和表尾是相等的。（ 0 ） 23、线性表可以看成是广义表的特例，如果广义表中的每个元素是原子，则广义表便成为线性表。（ 1 ） 24、插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也会经常使用。（ 0 ） 25、线索二叉树是一种物理结构。（ 1 ） 26、一个带权无向连通图的最小生成树有一棵或多棵。（ 1 ） 27、对线性表进行二分查找时，要求线性表必键值有序的链接表。（ 1 ） 29、树中所有结点的度等于所有结点数加1。（ 0 ） 30、图的深度优先搜索是一种典型的回溯搜索的例子，可以通过递归算法求解。（ 1 ） 三、填空题。 1、在一个带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为： p->next->next 。 2、有向图的边称为 弧 ，边的始点称为 弧尾 ，边的终点称为 弧头 。有向图顶点的度为 出度 和 入度 之和。 3、若一个算法中的语句频度之和为T（n）=3n+nlog2n+n2，则算法的时间复杂度为 O(T（n）)___ 。 4、如下程序段的时间复杂度为___O(m*n)___ for(i=1; i<=n; i++){ m=n-i; for (j=1; j<=m; j++) sum+=j; } 5、设某数据结构的二元组形式表示为A=(D，R)，D={1，2，3，4，5，6，7，8，9}，R={r}，r={<1，2>，<1，3>，<1，4>，<2，5>，<2，6>，<3，7>，<3，8>，<3，9>}，则该数据结构是____树形___结构。 6、从一个具有n个结点的单链表中查找值等于x的结点时，在查找成功的情况下，平均比较次数为：____(n+1)/2____。 7、在中序线索二叉树中，左线索指向 前驱或左孩子 。 8、对于一个以顺序实现的循环队列Q[0..m-1]，队头、队尾指针分别为f,r，其判空的条件是 f=r ，判满的条件是 (r+1)%m=f 。 9、若已知一个栈的进栈序列是1，2，3，? ，n，其输出序列为p1，p2，p3， ?，pn，若p1=n，则pi为___n-i+1____。 10、设有n个结点的完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号，则第i个结点的右孩子结点的编号为_____2n+1__。 11、在一棵二叉树中，如果度为2的结点有25个，则该树的叶子结点一定有____26____个。 12、在一个具有n个顶点的无向完全图中，包含有__n(n-1)/2__条边。 13、线性结构的逻辑特征是 除头结点和尾节点外每个节点仅有一个前驱和一个后继结点 。 14、设一组权值集合W={2，3，4，5，6}，则由该权值集合构造的哈夫曼树中带权路径长度之和为____45____ 15、设有向图G中有向边的集合E={<1，2>，<1，3>，<2，4>，<3，2>，<3，4>，<4，5>}，则该图的拓扑序列为_____13245____。 16、一个队列的入队序列是1，2，3，4，则出队序列为：__________1234____。17、设有一个顺序循环队列中有M个存储单元，则该循环队列中最多能够存储______M-1_____个队列元素。 18、队列Q，经过下列运算：InitQueue(Q)(初始化队列); InQueue(Q,a); InQueue(Q,b); DeQueue(Q, x); DeQueue(Q, x); 后x值是_______b_____。 19、数据结构包括了 数据的逻辑结构 、 数据的存储结构 、 数据的运算 三个方面的内容。 20、设一棵完全二叉树中有300个结点，则该二叉树的深度为____9____。 21、在一个具有n个顶点的有向完全图中，包含有____n*(n-1)__条边。 22、一棵深度为 10 的完全二叉树的结点总数的最小值为__2^9-1__，最大值为____2^10-1______。 23、有一个有序表{3，7，8，15，18，22，34， 67，75， 84，92，100},当用二分查找法查找键值为92的结点时，经____3__次比较后查找成功。 24、递归算法必须依赖 堆栈 的处理来实现。 25、队列的运算特点是 先进先出 ，栈的运算特点是 先进后出 。 26、设有向图G中有向边的集合E={<1，2>，<2，3>，<1，4>，<4，2>，<4，3>}，则该图的拓扑序列为______1423___。 27、在一个长度为n的顺序表L中，删除下标为i的结点，需要移动的结点数为____n-i-1__。 28、假设用front表示队头元素在一维数组中的前一位置，rear表示对尾元素在一维数组中的位置，则队列为空的条件是__front==rear____。 29、一棵含7个结点的完全二叉树的深度为___3____。 30、已知二维数组A[6][10]，每个数组元素占4个存储单元，若按行优先顺序存放数组元素a[3][5]的存储地址是1000，则a[0][0]的存储地址是______860___。 31、含n个顶点的无向连通图中至少含有____n-1__条边。 32、对于栈只能在___栈顶___插入和删除元素。 33、树是n个节点的有限集合，其中有且仅有一个___根__节点没有前趋节点，而包含度为0的节点称为___n+1/2__节点。 34、指向前趋节点和后继节点的指针称为线索，加了线索的二叉树称为___线索二叉树___。 35、常用的图的遍历方法有两种；深度优先搜索和____广度优先搜索_____。 36、为了能有效地应用HASH查找技术，必须解决的两个问题是____构造一个好的hash函数_____和___确定解决冲突的方法____。 37、顺序表中逻辑上相邻的元素的物理位置 相邻 。单链表中逻辑上相邻的元素的物理位置 不 相邻。 38、在一个长度为n的数组的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动 n-i 个元素。 四、简答题。 1、已知两个一元多项式A(x)和B(x)如下： A(x) = 3 + 5x + 7x5 + 9x15 B(x) = 4x – 7x5+ 21x7 要求给出图形示意表示： （1）采用单链表表示一元多项式A(x)和B(x) （2）给出求和A(x)+B(x)多项式的单链表（要求给出结点指针变化过程） 2、简述下列术语：数据，数据元素、数据对象、数据结构、存储结构。 3、简述栈和线性表的差别。 4、试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区 别。 5、已知一棵树边的集合为 {(i,m),(i,n),(e,i),(b,e),(b,d),(a,b),(g,j),(g,k),(c,g),(c,f),(h,l),(c,h),(a,c)}用树形表示法画出此树，并回答下列问题。 （1） 哪个是根结点？ a （2） 哪些是叶结点？ d m n j k f l （3） 哪个是g的双亲？ c （4） 哪些是g的祖先？ a b c （5） 哪些是g的孩子？ j k （6） 哪些是e的子孙？ i m n （7） 哪些是e的兄弟？哪些是f的兄弟？ dgfh degh （8） 结点b和n的层次各是多少？ 2 5 （9） 树的深度是多少？ 5 （10）以结点c为根的子树的深度是多少？ 2 （11）树的度是多少？ 3 6、何谓队列的“假溢出”现象，如何解决？ 7、简述队列和堆栈这两种数据类型的相同点和差异处。 8、线索二叉树的特点是什么？分别写出二叉树的先序，中序，后序遍历结果，并画出这个二叉树的中序线索链表图。a b c d e 先序：abdce 中序：bdaec 后序：dbeca 9、对于下图，试给出： （1）每个顶点的入度，出度。 d(1)+ = 1, d(1)- = 2 d(2)+ = 2, d(1)- = 2 d(3)+ = 3, d(3)- = 1 d(4)+ = 3, d(4)- = 0 d(5)+ = 2, d(5)- = 3 d(6)+ = 1, d(6)- = 2 （2）邻接矩阵和入边表图示。 （3）强连通分量。 1，23652，4 1 4 5 6 2 3