当前位置：搜档网 › 数据结构试卷B卷(含答案)

数据结构试卷B卷(含答案)

《数据结构》试卷B

一、填空题（每空1分，共15分）

1. 向量、栈和队列都是结构，可以在向量的位置插入和删除元素；对于栈

只能在插入和删除元素；对于队列只能在插入和删除元素。

2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为。不允许插入和删除

运算的一端称为。

3. 数据结构是一门研究非数值计算的程序设计问题中计算机的以及它们之间

的和运算等的学科。

4. 在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。

5. 在具有n个单元的循环队列中，队满时共有个元素。

6. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查

找成功的结点数为；比较四次查找成功的结点数为；平均查找长度为。

二、判断正误（判断下列概念的正确性，并作出简要的说明。）（每小题1分，共10分）

（）1. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。（）2. 在表结构中最常用的是线性表，栈和队列不太常用。

（）3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。

（）4. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。（）5.线性表的逻辑顺序与存储顺序总是一致的

（）6. 栈和队列是一种非线性数据结构。

（）7. 栈和队列的存储方式既可是顺序方式，也可是链接方式。

（）8. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。

（）9. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。

（）10. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。

三、单项选择题（每小题1分，共20分）

（）1．数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：（A ）存储结构（B ）逻辑结构（C ）顺序存储结构（D ）链式存储结构

（）2. 若已知一个栈的入栈序列是1，2，3，…，n ，其输出序列为p1，p2，p3，…，pn ，若p1=n ，则pi 为

Ａ．i Ｂ．n=i Ｃ．n-i+1 Ｄ．不确定

（）3. 判定一个栈ST （最多元素为m0）为空的条件是

Ａ．ST->top<>0 Ｂ．ST->top=0 Ｃ．ST->top<>m0 Ｄ．ST->top=m0 （）4设矩阵A 是一个对称矩阵，为了节省存储，将其下三角部分（如下图所示）按行序存放在一维数组B[ 1, n(n-1)/2 ]中，对下三角部分中任一元素a i,j (i ≤j), 在一维数组B 中下标k 的值是：

Ａ．i(i-1)/2+j-1 Ｂ．i(i-1)/2+j Ｃ．i(i+1)/2+j-1 Ｄ．i(i+1)/2+j

（）5．具有n(n>0)个结点的完全二叉树的深度为。

(Ａ) log 2(n) (Ｂ) log 2(n) (Ｃ) log 2(n) +1 (Ｄ) log 2(n)+1

（）6. 有8个结点的无向连通图最少有条边。

A ．5 B. 6 C. 7 D. 8

7. 数据结构反映了数据元素之间的结构关系。链表是一种 A ，它对于数据元素的插入和删除 B 。通常查找线性表数据元素的方法有 C 和 D 两种方法，其中 C 是一种只适合于顺序存储结构但 E 的方法；而 D 是一种对顺序和链式存储结构均适用的方法。

供选择的答案：

A ：①顺序存储线性表 ②非顺序存储非线性表 ③顺序存储非线性表 ④非顺序存储线性表

B ： ① 不需要移动结点，不需改变结点指针 ②不需要移动结点，只需改变结点指针

③只需移动结点，不需改变结点指针 ④既需移动结点，又需改变结点指针

C ：① 顺序查找 ②循环查找 ③条件查找 ④二分法查找

D ：① 顺序查找 ②随机查找 ③二分法查找 ④分块查找

E ：① 效率较低的线性查找 ②效率较低的非线性查找 ③效率较高的非线性查找 ④效率较高的线性查找

答案：A ＝ B ＝ C ＝ D ＝ E ＝

8. 散列法存储的基本思想是根据 A 来决定 B ，碰撞（冲突）指的是 C ，处理碰撞的两类主要方法是 D 。

供选择的答案

??????

????????=n n n n a a a a a a A ,2,1,2,21,21,1ΛΛ

A，B：①存储地址②元素的符号③元素个数④关键码值

⑤非码属性⑥平均检索长度⑦负载因子⑧散列表空间

C: ①两个元素具有相同序号②两个元素的关键码值不同，而非码属性相同

③不同关键码值对应到相同的存储地址④负载因子过大⑤数据元素过多D：①线性探查法和双散列函数法②建溢出区法和不建溢出区法

③除余法和折叠法④拉链法和开地址法

答案：A＝B＝C＝D＝

9. 考虑具有如下性质的二叉树：除叶子结点外，每个结点的值都大于其左子树上的一切结点的值。并小于等于其右子树上的一切结点的值。

现把9个数1，2，3，…，8，9填入下图所示的二叉树的9个结点中，并使之具有上述性质。此时，n1的值是A ，n2的值是 B ，n9的值是 C 。现欲把10放入此树

并使该树保持前述性质，增加的一个结点可以放在 D 或 E 。

供选择的答案

A～C：①1 ②2 ③3 ④4 ⑤5 ⑥6

⑦7 ⑧8 ⑨9

D～E：①n7下面②n8下面③n9下面

④n6下面⑤n1与n2之间⑥n2与n4之间

⑦n6与n9之间⑧n3与n6之间

答案：A＝B＝C＝

D＝E＝

四、简答题（每小题5分，共25分）

1. 说明线性表、栈与队的异同点。

2.试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列

3. 假设正读和反读都相同的字符序列为“回文”，例如，‘abba’和‘abcba’是回文，‘abcde’和‘ababab’则不是回文。假设一字符序列已存入计算机，请分析用线性表、堆栈和队列等方式正确输出其回文的可能性？

4. 试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？

5. 给定二叉树的两种遍历序列，分别是：

前序遍历序列：D，A，C，E，B，H，F，G，I；

中序遍历序列：D，C，B，E，H，A，G，I，F，

试画出二叉树B，并简述由任意二叉树B的前序遍历序列和中序遍历序列求二叉树B的思想方法。

五、阅读理解（每小题5分，共20分）

1、已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，请写出在P 结点后插入S结点的核心语句序列。

2、阅读下列算法，若有错，改正之。

1.写出下列程序段的输出结果（队列中的元素类型QElem Type为char）。

void main( ){

Queue Q; Init Queue (Q);

Char x=’e’; y=’c’;

EnQueue (Q,’h’); EnQueue (Q,’r’); EnQueue (Q,’y’);

DeQueue (Q,x); EnQueue (Q,x);

DeQueue (Q,x); EnQueue (Q,’a’);

while(!QueueEmpty(Q)){ DeQueue (Q,y);printf(y); };

Printf(x);

}

2.简述以下算法的功能（栈和队列的元素类型均为int）。

void algo3(Queue &Q){

Stack S; int d;

InitStack(S);

while(!QueueEmpty(Q)){

DeQueue (Q,d); Push(S,d);

};

while(!StackEmpty(S)){

Pop(S,d); EnQueue (Q,d);

}

六、算法设计（每小题5分，共15分。至少要写出思路）

1. 写出在顺序存储结构下将线性表逆转的算法，要求使用最少的附加空间。

2. 编写程序，将若干整数从键盘输入，以单链表形式存储起来，然后计算单链表中结点的个数（其中指针P 指向该链表的第一个结点）。

3. 试写一个算法，判别读入的一个以‘@’为结束符的字符序列是否是“回文”。

答案

一、填空题（每空1分，共15分）

1.向量、栈和队列都是线性结构，可以在向量的任何位置插入和删除元素；对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插入和队首删除元素。

2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为栈顶。不允许插入和删除运算的一端称为栈底。

3. 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科。

4. 在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与表长和该元素在表中的位置有关。

5. 在具有n 个单元的循环队列中，队满时共有 n-1 个元素。

8. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为 2 ；比较四次查找成功的结点数为 8 ；平均查找长度为

3.7 。

解：显然，平均查找长度＝O （log 2n ）<5次（25

）。但具体是多少次，则不应当按照公式 )1(log 12++=n n n ASL 来计算（即（21×log 221）/20＝4.6次并不正确！）。因为这是在假设n ＝2m -1的情况下推导出来的公式。应当用穷举法罗列：

全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74； ASL ＝74/20=3.7 ！！！

二、判断正误（判断下列概念的正确性，并作出简要的说明。）（每小题1分，共10分）（ × ）1. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。

错，线性表是逻辑结构概念，可以顺序存储或链式存储，与元素数据类型无关。

（ × ）2. 在表结构中最常用的是线性表，栈和队列不太常用。

错，不一定吧？调用子程序或函数常用，CPU 中也用队列。

（ √ ）3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。

（ √ ）4. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。

正确，都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。

（ × ） 5.线性表的逻辑顺序与存储顺序总是一致的

（ × ）6. 栈和队列是一种非线性数据结构。

错，他们都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。

（ √ ）7. 栈和队列的存储方式既可是顺序方式，也可是链接方式。

（ √ ）8. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两

个栈的栈底分别设在这片内存空间的两端。

（ × ）9. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。错，后半句不对。

（ × ）10. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。

错，有可能。

三、单项选择题（每小题1分，共20分）

（ C ）1．数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：

（A ）存储结构（B ）逻辑结构（C ）顺序存储结构（D ）链式存储结构（ C ）2.若已知一个栈的入栈序列是1，2，3，…，n ，其输出序列为p1，p2，p3，…，pn ，若p1=n ，则pi 为

Ａ．i Ｂ．n=i Ｃ．n-i+1 Ｄ．不确定

解释：当p1=n ，即n 是最先出栈的，根据栈的原理，n 必定是最后入栈的（事实上题目已经表明了），那么输入顺序必定是1，2，3，…，n ，则出栈的序列是n ，…，3，2，1。

（若不要求顺序出栈，则输出序列不确定）

（ B ）3、判定一个栈ST （最多元素为m0）为空的条件是

Ａ．ST->top<>0 Ｂ．ST->top=0 Ｃ．ST->top<>m0

Ｄ．ST->top=m0

( B )4、设矩阵A 是一个对称矩阵，为了节省存储，将其下三角部分（如下图所示）按行序存放在一维数组B[ 1, n(n-1)/2 ]中，对下三角部分中任一元素a i,j (i ≤j), 在一维数组B 中下标k 的值是：

Ａ．i(i-1)/2+j-1 Ｂ．i(i-1)/2+j Ｃ．i(i+1)/2+j-1 Ｄ．i(i+1)/2+j

（ C ）5．具有n(n>0)个结点的完全二叉树的深度为。

(Ａ) log 2(n) (Ｂ) log 2(n) (Ｃ) log 2(n) +1 (Ｄ) log 2(n)+1

（ C ）6. 有8个结点的无向连通图最少有条边。

A ．5 B. 6 C. 7 D. 8

7、答案：A ＝ ④ B ＝ ② C ＝ ④ D ＝ ① E ＝ ③

8、答案：A ＝ ④ B ＝ ① C ＝ ③ D ＝ ④

9、答案：A ＝ ⑦ B ＝ ④ C ＝ ⑥ D ＝ ② E ＝ ⑥ ??????

????????=n n n n a a a a a a A ,2,1,2,21,21,1ΛΛ

四、简答题（每小题4分，共20分）

1.说明线性表、栈与队的异同点。

刘答：相同点：都是线性结构，都是逻辑结构的概念。都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表，只是对插入、删除运算加以限制。

不同点：①运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入、删除运算，因而是后进先出表LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。

②用途不同，堆栈用于子程调用和保护现场，队列用于多道作业处理、指令寄存及其他运算等等。

2. 试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。

答：DLR：A B D F J G K C E H I L M

LDR: B F J D G K A C H E L I M

LRD：J F K G D B H L M I E C A

3.假设正读和反读都相同的字符序列为“回文”，例如，‘abba’和‘abcba’是回文，‘abcde’和‘ababab’则不是回文。假设一字符序列已存入计算机，请分析用线性表、堆栈和队列等方式正确输出其回文的可能性？

答：线性表是随机存储，可以实现，靠循环变量（j--）从表尾开始打印输出；

堆栈是后进先出，也可以实现，靠正序入栈、逆序出栈即可；

队列是先进先出，不易实现。

哪种方式最好，要具体情况具体分析。若正文在机内已是顺序存储，则直接用线性表从后往前读取即可，或将堆栈栈顶开到数组末尾，然后直接用POP动作实现。（但堆栈是先减后压还是……）

若正文是单链表形式存储，则等同于队列，需开辅助空间，可以从链首开始入栈，全部压入后再依次输出。

4.试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？

答：①顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。

优点：存储密度大（＝1？），存储空间利用率高。缺点：插入或删除元素时不方便。

②链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针

优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小（<1），存储空间利用率低。

顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。

若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；

若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。

5.给定二叉树的两种遍历序列，分别是：

前序遍历序列：D ，A ，C ，E ，B ，H ，F ，G ，I ；中序遍历序列：D ，C ，B ，E ，H ，A ，G ，I ，F ，

试画出二叉树B ，并简述由任意二叉树B 的前序遍历序列和中序遍历序列求二叉树B 的思想方法。

解：方法是：由前序先确定root ，由中序可确定root 的左、右子树。然后由其左子树的元素集合和右子树的集合对应前序遍历序列中的元素集合，可继续确定root 的左右孩子。将他们分别作为新的root ，不断递归，则所有元素都将被唯一确定，问题得解。

C F

E G

B H I

五、阅读理解（每小题5分，共20分。至少要写出思路）

答：此题答案不唯一，但若从已给定序列中挑选，则限制颇多。

(7) Q=P;

(11) P=L; (8) while(P->next!=Q)P=P->next; (10) P=Q; (4) S->next=P->next; P->next=S;

2、答：这是找结点后继的程序。

共有3处错误。

注：当rtag ＝1时说明内装后继指针，可直接返回，第一句无错。

当rtag ＝0时说明内装右孩子指针，但孩子未必是后继，需要计算。中序遍历应当先左再根再右，所以应当找左子树直到叶子处。r=r->lchild; 直到LTag=1；

应改为：while(!r->L tag)r=r->L child;

3.写出下列程序段的输出结果（队列中的元素类型QElem Type为char）。void main( ){

Queue Q; Init Queue (Q);

Char x=’e’; y=’c’;

EnQueue (Q,’h’); EnQueue (Q,’r’); EnQueue (Q, y);

DeQueue (Q,x); EnQueue (Q,x);

DeQueue (Q,x); EnQueue (Q,’a’);

while(!QueueEmpty(Q)){ DeQueue (Q,y);printf(y); };

Printf(x);

}

答：输出为“char”。

4.简述以下算法的功能（栈和队列的元素类型均为int）。

void algo3(Queue &Q){

Stack S; int d;

InitStack(S);

while(!QueueEmpty(Q)){

DeQueue (Q,d); Push(S,d);

};

while(!StackEmpty(S)){

Pop(S,d); EnQueue (Q,d);

}

答：该算法的功能是：利用堆栈做辅助，将队列中的数据元素进行逆置。

六、算法设计（每小题5分，共15分。至少要写出思路）

1、输入：长度为n的线性表数组A(1:n)

输出：逆转后的长度为n的线性表数组A(1:n)。C语言描述如下（其中ET为数据元素的类型）：

2. 假设一个数组squ[m]存放循环队列的元素。若要使这m个分量都得到利用，则需另一个标志tag，以tag为0或1来区分尾指针和头指针值相同时队列的状态是“空”还是“满”。试编写相应的入队和出队的算法。

解：这就是解决队满队空的三种办法之①设置一个布尔变量以区别队满还是队空（其他两种见简答题）；

思路：一开始队空，设tag=0，若从rear一端加到与front指针相同时，表示入队已满，则令tag=1；

若从front一端加到与rear指针相同时，则令tag=0，表示出队已空。

3.试写一个算法判别读入的一个以‘@’为结束符的字符序列是否是“回文”。

答：编程如下：

int Palindrome_Test()//判别输入的字符串是否回文序列,是则返回1,否则返回0

{

InitStack(S);InitQueue(Q);

while((c=getchar())!='@')

{

Push(S,c);EnQueue(Q,c); //同时使用栈和队列两种结构

}

while(!StackEmpty(S))

{

Pop(S,a);DeQueue(Q,b));

if(a!=b) return ERROR;

}

return OK;

}//Palindrome_Test

数据结构试题及答案10套

一、单选题（每题 2 分，共20分） 1. 1.对一个算法的评价,不包括如下（B ）方面的内容。Ａ.健壮性和可读性Ｂ．并行性C。正确性Ｄ．时空复杂度 2.2．在带有头结点的单链表ＨL中,要向表头插入一个由指针p指向的结点，则执行（A ). Ａ. p－〉ｎｅxt=HL->nexｔ; ＨL-〉nexｔ=p; B． p-〉next=HL；ＨL=p；Ｃ。p-＞ｎext=HＬ； p＝HL；Ｄ. HL=p; ｐ－〉next＝ＨL； 3.3．对线性表,在下列哪种情况下应当采用链表表示？( B ）Ａ.经常需要随机地存取元素 B。经常需要进行插入和删除操作 C。表中元素需要占据一片连续的存储空间D．表中元素的个数不变 4. 4.一个栈的输入序列为１ 2 3，则下列序列中不可能是栈的输出序列的是( C ） A. 2 3 1 ??? B. ３ 2 1 C。 3 １ 2 ??? D. 1 ２３ 5. 5.AＯV网是一种（D ）。 A．有向图Ｂ．无向图Ｃ．无向无环图D．有向无环图 6.6。采用开放定址法处理散列表的冲突时,其平均查找长度（Ｂ)。 A．低于链接法处理冲突B．高于链接法处理冲突Ｃ.与链接法处理冲突相同 D。高于二分查找 7.7。若需要利用形参直接访问实参时，应将形参变量说明为（D ) 参数. Ａ。值Ｂ。函数 C.指针 D。引用 8.８．在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（ A )。 A。行号 B.列号 C．元素值 D．非零元素个数 9.9.快速排序在最坏情况下的时间复杂度为( D )。 A。O（loｇ 2n) B．Ｏ（nlog 2 n） C。０（n) D.0 （n2） 10.10.从二叉搜索树中查找一个元素时,其时间复杂度大致为( C ). Ａ．O(n） B. Ｏ(1） C。 O（log 2 n） D. O(n2)二、运算题（每题 6 分，共２４分）

数据结构与算法模拟试题

一、选择题 1.在逻辑上可以把数据结构分成（） A.线性结构和非线性结构 B.动态结构和静态结构 C.紧凑结构和非紧凑结构 D.内部结构和外部结构 2.单链表中各结点之间的地址（） A.必须连续 B.部分必须连续 C.不一定连续 D.以上均不对 3.在一个长度为n的顺序表中向第i个元素（0front==L C.P==NULL D.P->rear==L 12. 已知P为单链表中的非首尾结点，删除P结点的后继结点Q的语句为（）。 A.P->NEXT=Q->NEXT;FREE(Q); B.Q->NEXT=P; FREE(Q); C.Q->NEXT=P->NEXT;FREE(Q); D.P->NEXT=S;S->NEXT=P; 13.循环队列SQ队满的条件是（）。 A.SQ->rear==SQ->front B. (SQ->rear+1)%MAXLEN==SQ->front C.SQ->rear==0 D. SQ->front==0 14.一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为()。 A、79，46，56，38，40，80 B、84，79，56，38，40，46 C、84，79，56，46，40，38 D、84，56，79，40，46，38 15.排序趟数与序列原始状态(原始排列)有关的排序方法是（）方法。 A、插入排序 B、选择排序 C、冒泡排序 D、快速排序 16.下列排序方法中，（）是稳定的排序方法。 A、直接选择排序 B、二分法插入排序

数据结构试卷带答案

数据结构试卷（一）一、选择题（20分） 1．组成数据的基本单位是（ 1.C ）。 (A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量 2．设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构A是（ C ）。 (A) 线性结构(B) 树型结构(C) 图型结构(D) 集合 3．数组的逻辑结构不同于下列（D）的逻辑结构。 (A) 线性表(B) 栈(C) 队列(D) 树 4．二叉树中第i(i≥1)层上的结点数最多有（C）个。 (A) 2i (B) 2i(C) 2i-1(D) 2i-1 5．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（.A ）。 (A) p->next=p->next->next (B) p=p->next (C) p=p->next->next (D) p->next=p 6．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（.C ）。 (A) 6 (B) 4 (C) 3 (D) 2 7．将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（C ）。 (A) 100 (B) 40 (C) 55 (D) 80 8．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（8.B (A) 3 (B) 4 (C) 5 (D) 1 9．根据二叉树的定义可知二叉树共有（B）种不同的形态。 (A) 4 (B) 5 (C) 6 (D) 7 10.设有以下四种排序方法，则（B ）的空间复杂度最大。 (A) 冒泡排序(B) 快速排序(C) 堆排序(D) 希尔排序二、填空题(30分) 1.设顺序循环队列Q[0：m-1]的队头指针和队尾指针分别为F和R，其中队头指针F指向当前队头元素的前一个位置，队尾指针R指向当前队尾元素所在的位置，则出队列的语句为F =____________;。 2.设线性表中有n个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度为___________，在链式存储结构上实现顺序查找的平均时间复杂度为___________。 3.设一棵二叉树中有n个结点，则当用二叉链表作为其存储结构时，该二叉链表中共有________个指针域，__________个空指针域。 4.设指针变量p指向单链表中结点A，指针变量s指向被插入的结点B，则在结点A的后面插入结点 B的操作序列为______________________________________。 5.设无向图G中有n个顶点和e条边，则其对应的邻接表中有_________个表头结点和_________个表结点。 6.设无向图G中有n个顶点e条边，所有顶点的度数之和为m，则e和m有______关系。 7.设一棵二叉树的前序遍历序列和中序遍历序列均为ABC，则该二叉树的后序遍历序列为__________。 8.设一棵完全二叉树中有21个结点，如果按照从上到下、从左到右的顺序从1开始顺序编号，则编号为8的双亲结点的编号是___________，编号为8的左孩子结点的编号是_____________。 9.下列程序段的功能实现子串t在主串s中位置的算法，要求在下划线处填上正确语句。 int index(char s[ ], char t[ ]) { i=j=0; while(i

数据结构期中考试试题答案c语言版本

数据结构期中考试试题答案一、单选题（每小题2分，共8分） 1.在一个长度为n的线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（即x同元素的平均比较次数，假定查找每个元素的概率都相等）为 C 。 A.n B.n/2 C.(n+1)/2 D.(n-1)/2 2.在一个带附加表头的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行 D 。 A.HL=p;p->next=HL; B.p->next=HL;HL=p; C.p->next=HL;p=HL; D.p->next=HL->next;HL ->next=p; 3．若让元素A，B，C，D依次入栈，则出栈次序不可能出现 D 种情况。 A.D,C,B,A B.A,D,C,B C.B,A,D,C D.D,A,B,C 4．从一个顺序队列删除元素时，首先需要 B 。 A.前移一位队首指针 B.后移一位队首指针 C.取出队首指针所指位置上的元素 D.取出队尾指针所指位置上的元素二、填空题（每空1分，共32分） 1．数据的逻辑结构分为集合、线性、树型、图形四种。 2.函数重载要求参数个数、参数类型或参数次序有所不同。 3．在带附加表头的循环双向链表中，表头附加结点的左指针域指向最后一个结点，最后一个结点的右指针域指向表头附加结点。

4．在以HL为表头指针的带附加结点的单链表和循环单链表中，链表为空的条件分别为 HL->next==NULL 和 HL==HL->next 。 5．在由数组a中元素结点构成的单链表中，删除下标为i的结点后，需要把该结点插入到空闲表的表头，具体操作为 a[i].next=a[1].next 、a[1].next=i 。 6．在由数组a中元素结点构成的单链表中，删除下标为i的结点的后继结点并将被删除结点的下标赋给i时，所进行的操作（需要用一个临时变量p）描述为 p=a[i].next 和 a[i].next=a[p].next;i=p 。 7．在稀疏矩阵的十字链接存储中，每个结点的down指针域指向列号相同的下一个结点，right指针域指向行号相同的下一个结点。 8．一个广义表中的元素分为单元素和表元素两类。 9．广义表A=((a,(b,(),c),((d),e)))的长度为 1 ，深度为 4 。 10．向一个顺序栈插入一个元素时，首先应 top++ ，然后再将待插入元素放入栈顶位置。 11．对于队列，应在队尾进行插入，在队首进行删除。 12．中缀表达式2+7/(4-1)所对应的后缀表达式为 2 7 4 1 - / + @ 。 13．后缀表达式“10 3 5 4 - * - 1 + 3 2 + -”的值为 3 。 14.一棵二叉树的广义表表示为a(b(c,d),e(f(,g))),则e结点的双亲结点为 a ，孩子结点为 f ，树的深度为 4 。三、运算题（每小题8分，共24分） 1．假定线性表L=（33,69,78,22,44,88）,i=3,x=34,y=22,则对L进行下列一组操作` ListEmpty(L); false GetElem(L,i); 78

数据结构试卷带答案

数据结构试卷带答案问题说明部分题目或答案有问题，现将已经发现的公布如下，同学在作这些模拟题的时候应着重做题方法的理解，遇到问题以教材或课件为准，不确定的地方可找同学商量或问我（1）试卷1第一套填空题第1题，试卷1第2套选择题第3题关于循环队列队头指针和队尾指针的约定与教材不一致，以教材或课件为准，实际上front指向的是队头元素，rear指向当前尚未被占用的第一个队列空间，队慢或队空的判定条件及入队/出队等操作具体可参考课件或教材（2）试卷1第一套应用题第5题，不声明邻接点顺序时默认编号最小的邻接点为第一邻接点，该图的深度优先遍历序列为123465,答案错。此外，当给定邻接表时则邻接点顺序按照邻接表中的前后顺序确定，如试卷1第二套填空题第8题（3）试卷1第五套应用题第4题，两种方法处理冲突的方法下所求ASL值相等都为7/6 （4）试卷1第五套填空题第8题答案给出的是小顶堆需满足的条件，大顶堆满足ki>=k2i p->rlink->llink=p->llink;此外，注意课堂中讲的指针名和操作方法（12）第4套填空题第6题答案错，设哈夫曼树中共有99个结点，则该树中有____50_____个叶子结点；若采用二叉链表作为存储结构，则该树中有__100___个空指针域。

（13）第5套选择第8题答案应为A:设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发可以得到一种深度优先遍历的顶点序列为(A) abedfc (14)第5套应用题第3题题目未指明查找方法，没法作（15）第6套选择第5题应选B，实际是任意结点至多只有一个孩子：设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是(B) 高度等于其结点数（16）第7套填空1题问题本身错，设指针变量p指向双向链表中的结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为____s->left_____=p；s->right=p->right；___p->right_______=s；s->right->left=s；（设结点中的两个指针域分别为left和right）。（17）第8套填空题第8题答案错（18）第7套选择第3题题目错，应以60为基准关键字，答案为C．设一组初始记录关键字序列为(60，80，55，40，42，85)，则以第一个关键字60为基准而得到的一趟快速排序结果是（）。 (C) 42，40，55，60，80，85 （17）第6套填空9题．快速排序算法的空间复杂度平均情况下为_O(logn)_，最坏的情况下为_O(n)_。(18)第9套填空第3题，题目说循环队列有m个元素实际指循环队列总长为m，此外，该题关于队头和队尾指针的约定不同于教材（19）第9套填空第4题答案错，9个元素冒泡排序，第一趟比较次数为8，最多8趟

数据结构与算法分析习题与参考答案

大学《数据结构与算法分析》课程习题及参考答案模拟试卷一一、单选题（每题 2 分，共20分） 1.以下数据结构中哪一个是线性结构？( ) A. 有向图 B. 队列 C. 线索二叉树 D. B树 2.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点，则执行如下( )语句序列。 A. p=q; p->next=q; B. p->next=q; q->next=p; C. p->next=q->next; p=q; D. q->next=p->next; p->next=q; 3.以下哪一个不是队列的基本运算？（） A. 在队列第i个元素之后插入一个元素 B. 从队头删除一个元素 C. 判断一个队列是否为空 D.读取队头元素的值 4.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成( ) 个不同的字符串？ A.14 B.5 C.6 D.8 5.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为( )。以下6-8题基于图1。 6.该二叉树结点的前序遍历的序列为( )。 A.E、G、F、A、C、D、B B.E、A、G、C、F、B、D C.E、A、C、B、D、G、F D.E、G、A、C、D、F、B 7.该二叉树结点的中序遍历的序列为( )。 A. A、B、C、D、E、G、F B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F E.B、D、C、A、F、G、E 8.该二叉树的按层遍历的序列为( )。

A．E、G、F、A、C、D、B B. E、A、C、B、D、G、F C. E、A、G、C、F、B、D D. E、G、A、C、D、F、B 9.下面关于图的存储的叙述中正确的是( )。 A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关 C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关 D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 10.设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述序列出发建堆的结果?( ) A. a，g，h，m，n，p，q，x，z B. a，g，m，h，q，n，p，x，z C. g，m，q，a，n，p，x，h，z D. h，g，m，p，a，n，q，x，z 二、填空题（每空1分，共26分） 1.数据的物理结构被分为_________、________、__________和___________四种。 2.对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为_________，在表尾插入元素的时间复杂度为____________。 3.向一个由HS指向的链栈中插入一个结点时p时，需要执行的操作是________________; 删除一个结点时，需要执行的操作是______________________________（假设栈不空而且无需回收被删除结点）。 4.对于一棵具有n个结点的二叉树，一个结点的编号为i(1≤i≤n)，若它有左孩子则左孩子结点的编号为________，若它有右孩子，则右孩子结点的编号为________，若它有双亲，则双亲结点的编号为________。 5.当向一个大根堆插入一个具有最大值的元素时，需要逐层_________调整，直到被调整到____________位置为止。 6.以二分查找方法从长度为10的有序表中查找一个元素时，平均查找长度为________。 7.表示图的三种常用的存储结构为_____________、____________和_______________。 8.对于线性表（70，34，55，23，65，41，20）进行散列存储时，若选用H（K）=K %7 作为散列函数，则散列地址为0的元素有________个，散列地址为6的有_______个。 9.在归并排序中，进行每趟归并的时间复杂度为______，整个排序过程的时间复杂度为 ____________，空间复杂度为___________。 10.在一棵m阶B_树上，每个非树根结点的关键字数目最少为________个，最多为________ 个，其子树数目最少为________，最多为________。三、运算题（每题 6 分，共24分） 1.写出下列中缀表达式的后缀形式：（1）3X/(Y-2)+1 （2）2+X*(Y+3) 2.试对图2中的二叉树画出其： (1)顺序存储表示的示意图； (2)二叉链表存储表示的示意图。 3.判断以下序列是否是小根堆? 如果不是, 将它调图2 整为小根堆。（1）{ 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 } （2）{ 05, 23, 20, 28, 40, 38, 29, 61, 35, 76, 47, 100 } 4.已知一个图的顶点集V和边集E分别为： V={1,2,3,4,5,6,7};

数据结构试题及答案

第一章概论一、选择题 1、研究数据结构就是研究（Ｄ）。Ａ. 数据的逻辑结构?B。数据的存储结构 C。数据的逻辑结构和存储结构?D．数据的逻辑结构、存储结构及其基本操作(研究非数值计算的程序设计问题中，计算机操作对象以及他们之间的关系和操作) 2、算法分析的两个主要方面是（Ａ）。 A．空间复杂度和时间复杂度???B。正确性和简单性 C。可读性和文档性D．数据复杂性和程序复杂性 3、具有线性结构的数据结构是（ D ）。(线性结构就是：在非空有限集合中，存在为一个被称为第一个的数据元素和最后一个元素,有除了第一个元素，集合中每一个元素均只有一个前驱，除了最后一个元素有唯一后继)（链表、栈、队列、数组、串） A. 图Ｂ. 树??C．广义表(线性表的推广) D．栈 4、计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、（ B ）等5个特性。Ａ．可执行性、可移植性和可扩充性? B. 可执行性、有穷性和确定性 C。确定性、有穷性和稳定性??? D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是( C ）。 for(i=0；i

数据结构试题(含答案)

一．是非题（正确的打“√”，错误的打“×”。） 1. 数据结构可用三元式表示（D，S，P）。其中：D是数据对象，S是D上的关系， P是对D的基本操作集。× 2. 线性表的链式存储结构具有可直接存取表中任一元素的优点。× 3. 字符串是数据对象特定的线性表。 4. 二叉树是一棵结点的度最大为二的树。× 5．邻接多重表可以用以表示无向图，也可用以表示有向图。× 6．可从任意有向图中得到关于所有顶点的拓扑次序。× 7．一棵无向连通图的生成树是其极大的连通子图。× 8．二叉排序树的查找长度至多为log2ｎ。× 9．对于一棵m阶的B-树.树中每个结点至多有m 个关键字。除根之外的所有非终端结点至少有┌m/2┐个关键字。× 10．对于目前所知的排序方法，快速排序具有最好的平均性能。 11. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。× 12. 二维数组是其数据元素为线性表的线性表。 13. 连通图G的生成树是一个包含G的所有n个顶点和n-1条边的子图。× 14. 折半查找不适用于有序链表的查找。 15. 完全二叉树必定是平衡二叉树。 16. 中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。 17. 队列是与线性表完全不同的一种数据结构。× 18. 平均查找长度与记录的查找概率有关。 19. 二叉树中每个结点有两个子结点，而对一般的树，则无此限制，所以，二叉树是树的特殊情形。× 20. 算法的时间复杂性越好，可读性就越差；反之，算法的可读性越好，则时间复杂性就越差。× 二．选择题 1. 若对编号为1，2，3的列车车厢依次通过扳道栈进行调度，不能得到 ( e ) 的序列。 a:1,2,3 b:1,3,2 c:2,1,3 d:2,3,1 e:3,1,2 f:3,2,1 2. 递归程序可借助于( b )转化为非递归程序。 a:线性表 b: 栈 c:队列 d:数组 3. 在下列数据结构中( c )具有先进先出（FIFO）特性， ( b )具有先进后出(FILO）特性。 a:线性表 b:栈 c:队列 d:广义表 4. 对字符串s=’data-structure’ 执行操作replace(s,substring(s,6,8),’bas’)

数据结构与算法试题

数据结构与算法试题一、单选题 1、在数据结构的讨论中把数据结构从逻辑上分为 (C ) A 内部结构与外部结构 B 静态结构与动态结构 C 线性结构与非线性结构 D 紧凑结构与非紧凑结构。 2、采用线性链表表示一个向量时,要求占用的存储空间地址(D ) A 必须就是连续的 B 部分地址必须就是连续的 C 一定就是不连续的 D 可连续可不连续 3、采用顺序搜索方法查找长度为n的顺序表时,搜索成功的平均搜索长度为( D )。 A n B n/2 C (n-1)/2 D (n+1)/2 4、在一个单链表中,若q结点就是p结点的前驱结点,若在q与p之间插入结点s,则执行( D )。 A s→link = p→link;p→link = s; B p→link = s; s→link = q; C p→link = s→link;s→link = p; D q→link = s;s→link = p; 5、如果想在4092个数据中只需要选择其中最小的5个,采用( C )方法最好。 A 起泡排序 B 堆排序 C 锦标赛排序 D 快速排序 6、设有两个串t与p,求p在t中首次出现的位置的运算叫做( B )。 A 求子串 B 模式匹配 C 串替换 D 串连接 7、在数组A中,每一个数组元素A[i][j]占用3个存储字,行下标i从1到8,列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中,则存放该数

组至少需要的存储字数就是( C )。 A 80 B 100 C 240 D 270 8、将一个递归算法改为对应的非递归算法时,通常需要使用( A )。 A 栈 B 队列 C 循环队列 D 优先队列 9、一个队列的进队列顺序就是1, 2, 3, 4,则出队列顺序为( C )。 10、在循环队列中用数组A[0、、m-1] 存放队列元素,其队头与队尾指针分别为front与rear,则当前队列中的元素个数就是( D )。 A ( front - rear + 1) % m B ( rear - front + 1) % m C ( front - rear + m) % m D ( rear - front + m) % m 11、一个数组元素a[i]与( A )的表示等价。 A *(a+i) B a+i C *a+i D &a+i 12、若需要利用形参直接访问实参,则应把形参变量说明为( B )参数。 A 指针 B 引用 C 值 D 变量 13、下面程序段的时间复杂度为( C ) for (int i=0;i

数据结构期中试卷信息11)2015-1-21 16.12.11

嘉兴学院试卷 2012—2013 学年第1 学期期中考试试卷课程名称：数据结构使用班级：信息11级考试形式：开卷试卷代码：班级：姓名：学号：一、单项选择题(在每小题的四个备选答案中，选出一个正确答案，并将正确答案的序号填在题干的括号内。每小题1分，共10分) 1．数据的逻辑结构从形式上可用二元组（D，R）表示，其中R是（ D ）的有限集。 A．算法B．数据元素C．数据操作D．数据关系 2．数据结构课程研究的内容涉及到三个方面的内容，它们分别是数据的逻辑结构、数据的（C）和数据的操作。 A．数据元素B．逻辑结构C．存储结构D．计算方法 3．线性结构的顺序存储结构是一种随机存取的存储结构，而链式存储结构是一种（ A ）的存储结构。 A．顺序存取 B．随机存取 C．索引存取 D．散列存取 4．线性表L在（ B ）情况下，最适合采用链式存储结构来实现算法。 A．不需经常对L进行修改 B．需经常对L进行删除和插入操作 C．需经常修改L中结点值 D．L中结点结构复杂 5．在一个含有n个结点的有序单链表中插入一个新结点，使单链表仍然保持有序的算法的时间复杂度是（ C ）。 A.O(1) B. O(log2n) C. O(n) D. O(n2) 6．在循环顺序队列中，假设以设置一个计数变量num的方法来区分队列判满和判空的条件，front和rear 分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则下面不是队列判满或判空条件是（ A ）。 A．front==rear B. front= =rear && num==0 C. front= =rear && num>0 D. num= =maxSize 7．一个栈的入栈序列是a, b, c, d, e, 则栈的不可能的出栈序列是（ D ）。 A．abcde B．decba C．edcba D．dceab 8．在顺序栈中，若栈顶指针top指向栈顶元素的下一个存储单元，且顺序栈的最大容量是maxSize。则顺序栈的判满的条件是（ C ）。 A．top = =0 B.top= =-1 C. top = =maxSize D.top = = maxSize-1 9．设线性表有n个元素，严格说来，以下操作中，（ B ）在顺序表上实现比链表上实现比链表上实现效率更高。 Ⅰ输出第i个（0≤i≤n-1）数据元素的值 Ⅱ交换第3个数据元素与第4个数据元素的值 Ⅲ顺序输出这n个数据元素的值 A．Ⅰ B．Ⅰ、Ⅱ C．Ⅰ、Ⅲ D．Ⅱ、Ⅲ 10. 在一个单链表中的p和q两个结点之间插入一个新结点，假设新结点为s,则修改链的Java语句序列是（ D ）。 A．s.setNext(p); q.setNext(s); B. p.setNext(s.getNext()); s.setNext(p); C. q.setNext(s.getNext()); s.setNext(p); D. p.setNext(s); s.setNext(q); 二、填空题（20分，每空1分） 1．算法的复杂度通常体现为时间复杂度和空间复杂度两个指标。 2．设有函数T (n)=3n2-n+4，T (n)=O ( n2)。 3．要将一个顺序表{a0,a1,……,a n-1}中第i个数据元素a i(0≤i≤n-1)删除，会引起n-1-i个数据元素的移动。 4．队列也是一种操作受限的线性表，它与栈不同的是，队列中所有的插入操作均限制在表的一端进行，而所有的删除操作都限制在表的另一端进行，允许插入的一端称为队尾，允许删除的一端称为队首。队列具有先进先出的特点。 5．在一个单链表中删除p所指结点时，可执行如下操作： q=p.getNext(); p.setData(q.getData());p.setNext( q.getNext() ); 6．设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出栈的序列是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是3。 7．若双向链表的结点类描述为：public class DuLNode { pvivate Object data; private DuLNode piror; private DuLNode next; …… } 则在带头结点的双向链表中的p结点之前插入一个新结点s，其修改指针的java语句序列是： 1）p.getPiror().setNext(s); 2）s.setPiror(p.gettPiror()); 3）s.setNext(p); 4）p.setPiror(s); 8．在不带表头结点的链栈中，栈顶指针top直接指向栈顶元素，如果链栈中结点的类描述为： class Node { 命题人或命题小组负责人签名：所（室、教研部）负责人签名：分院（部）领导签名：

数据结构试卷B卷(含答案)

《数据结构》试卷B 一、填空题（每空1分，共15分） 1. 向量、栈和队列都是结构，可以在向量的位置插入和删除元素；对于栈只能在插入和删除元素；对于队列只能在插入和删除元素。 2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为。不允许插入和删除运算的一端称为。 3. 数据结构是一门研究非数值计算的程序设计问题中计算机的以及它们之间的和运算等的学科。 4. 在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。 5. 在具有n个单元的循环队列中，队满时共有个元素。 6. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为；比较四次查找成功的结点数为；平均查找长度为。二、判断正误（判断下列概念的正确性，并作出简要的说明。）（每小题1分，共10分）（）1. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。（）2. 在表结构中最常用的是线性表，栈和队列不太常用。（）3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。（）4. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。（）5.线性表的逻辑顺序与存储顺序总是一致的（）6. 栈和队列是一种非线性数据结构。（）7. 栈和队列的存储方式既可是顺序方式，也可是链接方式。（）8. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。（）9. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。

国家二级ACCESS机试选择题(数据结构与算法)模拟试卷15

国家二级ACCESS机试选择题（数据结构与算法）模拟试卷15 (总分：64.00，做题时间：90分钟) 一、选择题(总题数：32，分数：64.00) 1.设循环队列为Q(1：m)，其初始状态为front=rear=m。经过一系列入队与退队运算后，front=15，rear=20。现要在该循环队列中寻找最大值的元素，最坏情况下需要比较的次数为（分数：2.00） A.4 √ B.6 C.m-5 D.m-6 解析：解析：初始状态为：front=rear=m，rear-front=0，此时队列为空。经过一系列入队与退队运算后，front=15，rear=20。队尾大于队头，则队尾rear减队头front等于5个元素。此时队列中有5个元素，而查找最大项至少要比较n．1次，就是4次。因此选项A正确。 2.下列叙述中正确的是（分数：2.00） A.循环队列属于队列的链式存储结构 B.双向链表是二叉树的链式存储结构 C.非线性结构只能采用链式存储结构 D.有的非线性结构也可以采用顺序存储结构√ 解析：解析：顺序存储方式不仅能用于存储线性结构，还可以用来存放非线性结构。例如，完全二叉树是属于非线性结构，但其最佳存储方式是顺序存储方式。 3.某二叉树中有n个叶子结点，则该二叉树中度为2l的结点数为（分数：2.00） A.n+1 B.n-1 √ C.2n D.n／2 解析：解析：任意一棵二叉树，如果叶结点数为N 0，而度数为2的结点总数为N 2，则N 0 =N 2 +1；N 2 =N 0 -1。所以如果二叉树中有n个叶子结点，则该二叉树中度为2的结点数为n-1。因此选项B正确。4.下列叙述中错误的是（分数：2.00） A.算法的时间复杂度与算法所处理数据的存储结构有直接关系 B.算法的空间复杂度与算法所处理数据的存储结构有直接关系 C.算法的时间复杂度与空间复杂度有直接关系√ D.算法的时间复杂度与空间复杂度没有必然的联系解析：解析：算法的时间复杂度，是指执行算法所需要的计算工作量。算法的空间复杂度，是指执行这个算法所需要的内存空间。两者与算法所处理数据的存储结构都有直接关系，但两者之间没有直接关系，因此选项C错误。 5.设栈的顺序存储空间为S(0：49)，栈底指针bottom=49，栈顶指针top=30(指向栈顶元素)。则栈中的元素个数为（分数：2.00） A.30 B.29 C.20 √ D.19

数据结构试题(含答案)

数据结构试题（含答案） 1．数据逻辑结构包括线性结构、树形结构和图状结构三种类型，树形结构和图状结构合称非线性结构 2．数据的逻辑结构分为集合、线性结构、树形结构和图状结构 4种。 3．在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有 1 个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有 1 个后续结点。 4．线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。 5．在树形结构中，树根结点没有前驱结点，其余每个结点有且只有 1 个前驱结点；叶子结点没． 6．数据结构的基本存储方法是顺序、链式、索引和散列存储。有后续结点，其余每个结点的后续结点可以任意多个。 7．衡量一个算法的优劣主要考虑正确性、可读性、健壮性和时间复杂度与空间复杂度。8．评估一个算法的优劣，通常从时间复杂度和空间复杂度两个方面考察。 9．算法的5个重要特性是有穷性、确定性、可行性、输入和输出。 10．在单链表中，要删除某一指定的结点，必须找到该结点的前驱结点。 11．在单链表中，要删除某一指定的结点，必须找到该结点的前驱结点。 12．在双链表中，每个结点有两个指针域，一个指向前驱结点，另一个指向后继结点。13．在顺序表中插入或删除一个数据元素，需要平均移动 n 个数据元素，移动数据元素的个数与位置有关 14．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表的元素是，应采用顺序存储结构 15．根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成单链表和双链表。 16．顺序存储结构是通过下标表示元素之间的关系的；链式存储结构是通过指针表示元素之间的关系的 17．带头结点的循环链表L中只有一个元素结点的条件是 L->next->next=L 18．栈是限定仅在表尾进行插入或删除操作的线性表，其运算遵循后进先出的原则。19．空串是零个字符的串，其长度等于零。空白串是由一个或多个空格字符组成的串，其长度等于其包含的空格个数。 20．组成串的数据元素只能是单个字符。 21．一个子串”str”在主串”datastructure”中的位置是 5 。 22．字符串中任意个连续字符构成的部分称为该串的子串。 23．二维数组M的每个元素是6个字符组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要 540个字节；M的第8列和第5行共占108个字节24．稀疏矩阵一般的压缩存储方法有两种，即三元组表和十字链表。 25．广义表（（a），（（b），c），（（（d））））的长度是 3 ，深度是 4 。 26．在一棵二叉树中，度为零的结点的个数为n0，度为2 的结点的个数为n2，则有n0＝ n2+1 。 27．在有n个结点的二叉链表中，空链域的个数为__n+1__。 28．一棵有n个叶子结点的哈夫曼树共有__2n-1_个结点 29．深度为5的二叉树至多有 31 个结点。 30．若某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点个数为69 。

数据结构试题及答案

一、判断题： 1、线性表的逻辑顺序与物理顺序总是一致的。( ) 2、线性表的顺序存储表示优于链式存储表示。( ) 3、线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。( ) 4、二维数组是其数组元素为线性表的线性表。( ) 5、每种数据结构都应具备三种基本运算：插入、删除和搜索。( ) 6、数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个方面。( ) 7、线性表中的每个结点最多只有一个前驱和一个后继。（） 8、线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。（） 9、栈和队列逻辑上都是线性表。（） 10、单链表从任何一个结点出发，都能访问到所有结点（） 11、删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序树。（） 12、快速排序是排序算法中最快的一种。（） 13、多维数组是向量的推广。（） 14、一般树和二叉树的结点数目都可以为0。（） 15、直接选择排序是一种不稳定的排序方法。（） 16、98、对一个堆按层次遍历，不一定能得到一个有序序列。（） 17、在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1。（） 18、折半搜索只适用与有序表，包括有序的顺序表和有序的链表。（） 19、堆栈在数据中的存储原则是先进先出。（） 20、队列在数据中的存储原则是后进先出。（） 21、用相邻矩阵表示图所用的存储空间大小与图的边数成正比。（） 22、哈夫曼树一定是满二叉树。（） 23、程序是用计算机语言表述的算法。（） 24、线性表的顺序存储结构是通过数据元素的存储地址直接反映数据元素的逻辑关系。（） 25、用一组地址连续的存储单元存放的元素一定构成线性表。（） 26、堆栈、队列和数组的逻辑结构都是线性表结构。（） 27、给定一组权值，可以唯一构造出一棵哈夫曼树。（） 28、只有在初始数据为逆序时，冒泡排序所执行的比较次数最多。（）

数据结构试卷B卷(含答案)

数据结构试题及答案10套

数据结构与算法模拟试题

数据结构试卷带答案

最新数据结构期中试卷及答案

数据结构期中考试试题答案c语言版本

数据结构试卷带答案

数据结构与算法分析习题与参考答案

数据结构试题及答案

数据结构试题(含答案)

数据结构与算法试题

数据结构期中试卷信息11)2015-1-21 16.12.11

数据结构试卷B卷(含答案)

国家二级ACCESS机试选择题(数据结构与算法)模拟试卷15

数据结构试题(含答案)

数据结构试题及答案

相关文档

最新文档