发布时间 : 星期日 文章数据结构实验报告（华夏）更新完毕开始阅读3b8bbc00ccbff121dd368354
{ y= y*x; n=n–1; } return （y）; } 问题：
（1 ）该算法的功能是计算 （2）该算法的时间复杂度是
（3）若执行一次条件判断和执行一次赋值所需时间相同，都是一个单位时间， 则该算法的执行时间等于多少个单位时间。
5、单项选择题
（1）一个数据对象是____的集合。
A.相同类型的数据项 B.相同类型的数据元素 C.不同类型的数据项 D.不同类型的数据元素 （2）___是数据的基本单位。
A.数据项 B.关键字 C.数据元素 D.数据类型 （3）数据结构在计算机中的表示称为数据____。
A.对象 B.的存储结构 C.类型 D.元素 （4）下列程序段的时间复杂度为____。 { for(i=0；i<5；i++)
for(j=0；j A.O(5) B.O(5+n) C.O(n5 ) D.O(n) 第2章 线性表 1、简述线性表、单链表、双链表和循环链表各自的特点。 2、对于线性表的两种存储结构，若线性表中的结点总数基本稳定，并且很少进行插入和 删除操作，但要求以最快的速度存取表中元素，那么选用哪种存储结构？ 3、试编写一个计算头结点指针为L的单链表长度的算法。 4、试编写一个用顺序存储结构实现将两个有序表合并为一个有序表的算法。 5、设有三个结点的线性表L=(A,B,C)， 分别画出存储在单链表和双链表中的示意图。 6、若线性表有10000个结点， 每个结点的需占用2个存储单元，该线性表需要多大的存储空间？若第一个结点的地址为1000, 则第110个结点的起始地址是多少？删除线性表的第 30 个结点，有多少个结点移动？如何移动？在线性表第i处插入1 个结点呢？ 7、单项选择题 （1）设顺序表L中有n个元素，在表L中插入一个元素，需要平均移动的元素个数为： A. n B. n－1 C. n/2 D. (n－1)/2 （2）若线性表最常用的操作是存取第i个元素及其前趋的值，则采用______存储方 式节省时间。 A 单链表 B 双向链表 C 单循环链表 D 顺序表 (3) 线性表是具有n (n>=0)个 _____的有限序列。 A 字符 B 表元素 C 数据元素 D 数据项 (4) 从逻辑上，可以将数据结构分为_____两类。 A 动态表和静态表 B 顺序结构和链式结构 C 线性结构和非线性结构 D 动态结构和静态结构 （5） 在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句________。 A p->next＝（p->next）->next B p ＝ p->next C p->next＝ p D p＝（p->next）->next 第3章 栈与队列 1、简述以下算法的功能。 void a3 (queue &q) { stack s ; int d ; initstack (s) ; // 构造一个空栈s while (!queueempty (q)) // 当队q非空时 { dequeue(q, d) ; // 从队q删除一个元素保存在 d中 push (s, d) ; } // 将d中的元素插入到栈 s里 while (!stackempty (s)) // 当栈s非空 { pop (s, d) ; // 弹出栈s的顶元保存在 d中 enqueue (q, d) ; } // 将d插入到队 q的尾部 } 2、单项选择题 （1）将递归算法转换成对应的非递归算法时，通常需要使用： A. 栈 B. 队列 C. 链表 D. 二叉树 （2）元素abcd依次进栈，则不能得到的出栈序列是： A. abcd B. badc C. dbca D. dcba （3）队列结构实现的是____________ A. 先进/后出 B.先进/先出 C. 后进/先出 D. 先来先服务 （4）若数组S[1..manx]作为栈S存储空间，TOP为栈指针，则栈满的条件 是______，栈空是____________。 A top=1 B top=0 C top=manx D top=manx+1 （5） 栈和队列的共同点是_______。 A．都是先进后出 B．都是先进先出 C．只能在端点处进行操作 D．各不相同 3、什么是队列的“假溢出”现象？如何解决？ 4、设有一空栈，现输入序列为1,2,3,4,5,经过push,push,pop,push,pop,push,pop,push，pop,pop,后，输出序列是什么？ 5、 写出以下程序段的输出结果。 void main () { queue q ; char x = 'e' ; char y = 'c' ; initqueue (q) ; // 构造一个空队列q enqueue (q, 'h' ) ; // 将元素h到队 q的尾部 enqueue (q, 'r' ) ; enqueue (q, y ) ; dequeue (q, x ) ; // 删除队q的队首元素x enqueue (q, x ) ; dequeue (q, x ) ; enqueue (q, 'a' ) ; while ( !queueempty (q) ) // 当队q非空 { dequeue(q, y) ; printf (y) ; } printf (x) ; } 第4章 串 1、简述空串与空格串、串变量与串常量、主串与子串、串名与串值每对术语的区别？ 2、两个字符串相等的充要条件是什么？ 3、串有哪几种存储结构？ 4、已知两个串：s1=”fg cdb cabcadr”, s2=”abc”, 试求两个串的长度，判断串s2是否是串s1的子串，并指出串s2在串s1中的位置。 5、已知：s1=〃I’m a student〃，s2=〃student〃，s3=〃teacher〃，试求下列各运算的结果： strstr(s1,s2)； strlen(s1)； strcat(s2,s3)； delstr(s1,4,10)； 6、空格串与空串有何区别? 举例说明之。 第5章 数组与广义表 1、填空题 （1）设数组A[1..8,1..10]的首地址为100，每个元素占4个存储单元，若以行序为主顺 序存储，则元素A[2,6]的存储地址为__________。 （2）设数组A[1..8,1..10]的首地址为200，每个元素占4个存储单元，若以列序为主顺序 存储，则元素A[4,6]的存储地址为__________。 （3）一个5*5的对称矩阵进行压缩存储，需要存储______个元素。 （4）稀疏矩阵的压缩存储可以采用_____方式。 2、画出广义表A=(( ),(e),(a,(b,c,d)))的存储结构图。 3、已知一个二维数组A[6][3],画出按行序为主序的顺序存储结构。 4、画出数组A[1..2][0..2] 的以列序为主序的顺序存储结构。 5、画出表示下面稀疏矩阵A的三元组表和十字链表图。 第6章 树和二叉树 1、单项选择题 （1） 以知一棵二叉树的前序和中序序列分别为ABDEGCFH 和DBGEACHF 则该二叉树的后序序列为 ______。 GEDHFBCA (B) DGEBHFCA (C) ABCDEFGH (D) ACBFEDHG (2) 深度为K的满二叉树有_____个叶结点。 (A)K2-1 (B)2K-1-1 (C)2K-1 (D)2K-1 (3) 有8个叶子结点的二叉树有_____个度为2的结点。 (A) 7 (B) 16 (C) 64 (D) 9 (4) 深度为5的满二叉树有_____个结点。 (A) 32 (B) 15 (C) 31 (D) 16 （5）在有n个叶子结点的Huffman树中，度为2的结点个数为： (A) n－1 (B) 2n－1 (C). n (D). 0 （6） 树最适合用来表示_____ (A)有序数据元素 (B) 无序数据元素 (C) 元素间具有分支层次关系的数据 (D) 元素之间无联系的数据 （7）设n，m是二叉树上的两个结点，在中序遍历中，n在m前的条件是（ ）。 (A) n在m的右子树上 (B) n是m的祖先 (C) n在m的左子树上 (D) n是m的子孙 2、已知一棵二叉树的中序遍历序列为DBHEAFICG，前序遍历序列为ABDEHCFIG,请完成： （1）画出该二叉树。 （2）写出后序遍历该二叉树所得的结点序列。 3、设二叉树的顺序存储结构如下： 1 E 2 A 3 F 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ∧ ∧ ∧ G I ∧ ∧ ∧ ∧ B ∧ D ∧ H ∧ ∧ C （1）根据其存储结构，画出该二叉树。 （2）写出按前序、中序、后序遍历该二叉树所得的结点序列。 4、设有如下二叉树 5 36 15 38 35 40 45 50 65 75 46 70 42 43 85