20071数据结构A

全国2007年10月高等教育自学考试数据结构试题课程代码：02331一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。

错选、多选或未选均无分。

1.下面程序段的时间复杂度为( )s=0；for(i=1；i<n；i++)for(j=1；j<i；j++)s+=i*j；A.O(1)B.O(logn)C.O(n)D.O(n2)2.已知指针p和q分别指向某单链表中第一个结点和最后一个结点。

假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为( )A.q->next=s->next；s->next=p；B.s->next=p；q->next=s->next；C.p->next=s->next；s->next=q；D.s->next=q；p->next=s->next；3.在计算机内实现递归算法时所需的辅助数据结构是( )A.栈B.队列C.树D.图4.假设以数组A[m]存放循环队列的元素。

已知队列的长度为length，指针rear指向队尾元素的下一个存储位置，则队头元素所在的存储位置为( )A.(rear-length+m+1)％mB.(rear-length+m)％mC.(rear-length+m-1)％mD.(rear-length)％m5.通常将链串的结点大小设置为大于1是为了( )A.提高串匹配效率B.提高存储密度C.便于插入操作D.便于删除操作6.带行表的三元组表是稀疏矩阵的一种( )A.顺序存储结构B.链式存储结构C.索引存储结构D.散列存储结构7.表头和表尾均为空表的广义表是( )A.()B.(())C.((()))D.(()，())8.用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为( )A.n-1B.nC.n+lD.2n9.为便于判别有向图中是否存在回路，可借助于( )A.广度优先搜索算法B.最小生成树算法C.最短路径算法D.拓扑排序算法10.连通网的最小生成树是其所有生成树中( )A.顶点集最小的生成树B.边集最小的生成树C.顶点权值之和最小的生成树D.边的权值之和最小的生成树11.按排序过程中依据的原则分类，快速排序属于( )A.插入类的排序方法B.选择类的排序方法C.交换类的排序方法D.归并类的排序方法12.下列关键字序列中，构成小根堆的是( )A.{84，46，62，41，28，58，15，37}B.{84，62，58，46，41，37，28，15}C.{15，28，46，37，84，41，58，62}D.{15，28，46，37，84，58，62，41}13.在长度为32的有序表中进行二分查找时，所需进行的关键字比较次数最多为( )A.4B.5C.6D.714.假设在构建散列表时，采用线性探测解决冲突。

一、（本题10分）（1）简述线性表的两种存储结构的主要优缺点及各自适用的场合。

（2）在折半查找和表插入排序中，记录分别应使用哪种存储结构，并用一句话简述理由。

答：（1）顺序存储是按索引（如数组下标）来存取数据元素，优点是可以实现快速的随机存取，缺点是插入与删除操作将引起元素移动，降低效率。

对于链式存储，元素存储采取动态分配，利用率高。

缺点是须增设指针域，存储数据元素不如顺序存储方便。

优点是插入与删除操作简单，只须修改指针域。

（2）在折半查找中，记录使用顺序存储，可以快速实现中点的定位；在表插入排序中，记录使用静态链表，可以降少移动记录的操作。

二、（本题15分）在带头结点的非空线性链表中，试设计一算法，将链表中数据域值最小的那个结点移到链表的最前面，其余各结点的顺序保持不变。

要求：不得额外申请新的链结点。

解：程序如下：typedef struct node {int data;struct node * next;}Node,*LinkList;void MinFirst(LinkList L){Node *p,*q,*ptrmin;if(L->next == NULL) return; //空表ptrmin = L; //ptrmin指向当前最小结点的前一个结点p = L->next;//p指向当前结点的前一个结点while(p->next!=NULL) {if( p->next->data < ptrmin->next->data ) ptrmin = p;p = p->next;}//q指向最小结点，并从链表中删除q = ptrmin->next; ptrmin->next = q->next;q->next = L->next; L->next = q; //q指向的最小结点插入到链表头}三、（本题15分）编写函数判断一棵二叉树是否不含有度为1的结点，若任何结点的度都不为1，则返回TRUE，否则返回FALSE。

2008－2009学年第二学期 计算机科学学院《数据结构》期末考试试卷（A 卷） 答案与评分标准 年级：07级 专业： 班级： 学号： 姓名： 题号 一 二 三 四 五 六 总分 签名 得分 注：1、共100分，考试时间120分钟。

2、此试卷适用于计算机科学与技术本科、信息管理与信息系统专业。

一 得 分 阅卷教师 2分，共20分） 1．数据是对客观事物的符号的表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的（ 符号的总称 ）。

2．抽象数据类型是指一个（ 数学模型 ）以及定义在该模型上的一组操作。

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

4. 顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的存储地址是（ 108 ）。

5．循环队列的引入是为了克服（ 假溢出 ）。

6．head(tail(head(((a ，b)，(c ，d)))))= b 。

7．已知一棵完全二叉树共有768个结点，则该树中有（ 384 ）个叶子结点。

8．某二叉树的先序遍历序列是8，5，1，3，2，4，6，7，10，9，11 ，中序遍历序列是1，2，3，4，5，6，7，8，9，10，11，则其后序遍历序列是（2，4，3，1，7，6，5，9，11，10，8）。

9．有向图G 用邻接矩阵存储，其第i 行的所有元素之和等于顶点i 的（ 出度 ）。

10．对n 个待排序记录序列进行快速排序，其最坏时间复杂度为（ O （n 2） ）。

二 得 分 阅卷教师 2分，共10分） 1．算法是指 （ A ） A ．对特定问题求解步骤的一种描述，是指令的有限序列 B ．计算机程序 C ．解决问题的计算方法 D ．数据处理 ——————————————装————————————————订————————————————线————————————2．若某线性表中最常用的操作是取第i个元素和查找第i个元素的前驱，则采用（A ）存储方法最节省时间。

注意事项：1、下面关于串的叙述中，哪一个是不正确的？（ ）A ．串是字符的有限序列B ．空串是由空格构成的串C ．模式匹配是串的一种重要运算D ．串既可以采用顺序存储，也可以采用链式存储 2、设无向图的顶点个数为n ，则该图最多有（ ）条边。

A ．n-1B ．n(n-1)/2C ． n(n+1)/2D ．0 3、以下数据结构中，（ ）是非线性数据结构。

A ．树B ．字符串C ．队列D ．栈 4、下面关于线性表的叙述中，错误的是哪一个？（ ）A ．线性表采用顺序存储，必须占用一片连续的存储单元。

B ．线性表采用顺序存储，便于进行插入和删除操作。

C ．线性表采用链接存储，不必占用一片连续的存储单元。

D ．线性表采用链接存储，便于插入和删除操作。

5、假设以数组A[m]存放循环队列的元素,其头尾指针分别为front 和rear ，则当前队列中的元素个数为（ ）。

A ．(rear-front+m)%mB ．rear-front+1C ．(front-rear+m)%mD ．(rear-front)%m6、在单链表指针为p 的结点之后插入指针为s 的结点,正确的操作是（ ）。

A ．p->next=s; s->next=p->next;B ．s->next=p->next; p->next=s;C ．p->next=s; p->next=s->next;D ．p->next=s->next; p->next=s; 7、设栈的输入序列是1，2，3，4,则（ ）不可能是其出栈序列。

A ．1，2，4，3B ．2，1，3，4C ．1，4，3，2D ．4，3，1，2， 8、广义表（a,(b,c),d,e ）的表头和表尾分别为（ ）。

A ．a 和(b,c),d,e B ．（a ）和(b,c),d,eC ．a 和 ((b,c)，d,e)D ．(a) 和((b,c)，d,e)9、栈和队都是（ ）A ．顺序存储的线性结构B ．链式存储的非线性结构C ．限制存取点的线性结构D ．限制存取点的非线性结构 10、从逻辑上可以把数据结构分为（ ）两大类。

中国人民公安大学2006~2007学年第二学期2005级侦查学专业计算机犯罪侦查专业方向《数据结构》期末考试卷（A卷）参考答案及评分标准一、判断题（正确的打“V”，错的打“X”。

每小题1分，共10分）1.（v）双向链表中至多只有一个结点的后继指针为空。

2.（x）在循环队列中，front指向队列中第一个元素的前一位置，rear指向实际的队尾元素，队列为满的条件是front=rear。

3.（v）对链表进行插入和删除操作时，不必移动结点。

4.（v）栈可以作为实现程序设计语言过程调用时的一种数据结构。

5.(x) 在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧<a,b>。

6.(x ) 对有向图G，如果从任一顶点出发进行一次深度优先或广度优先搜索就能访问每个顶点，则该图一定是完全图。

7.（x）“顺序查找法”是指在顺序表上进行查找的方法。

8.(v) 向二叉排序树插入一个新结点时，新结点一定成为二叉排序树的一个叶子结点。

9.（v）关键字序列{A，C，D，E，F，E，F}是一个堆。

10.（x）二路归并时，被归并的两个子序列中的关键字个数一定要相等。

二、填空题：(每小题2分,共 20分)1．一棵含有101个结点的完全二叉树存储在数组A[1..101]中, 对1≤k≤101, 若A[k]是非叶结点, 则k的最小值是：1。

2．设s=’YOU ARE JUDGING IT RIGHT OR WRONG’，顺序执行下列操作：SubString(sub1,s,1,8); SubString(sub2,s,20,5); StrCat(sub1,sub2);则最后sub1的值为：’YOU ARE RIGHT’。

3．若一个算法中的语句频度之和为T(n) = 3720n+4nlogn，则算法的时间复杂度为_ O(nlogn) ___ 。

4．广义表((((a),b),c),d)的表头是(((a),b),c) ，表尾是(d) 。

期末考试试卷（A）卷2007 ——2008 学年第一学期课程名称：数据结构适用年级/专业： 06/计应、计教试卷类别开卷（）闭卷（√）学历层次本科考试用时 120分钟《．考生．．．．．．．．．．．．．．．．．．．．．．．》．．．注意：答案要全部抄到答题纸上，做在试卷上不给分一、单项选择（每小题2分，共20分）（）1．算法的计算量的大小称为计算的（）。

A．可读性 B. 复杂性 C. 现实性 D. 难度（）2．链接存储的存储结构所占存储空间：A．分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针B．只有一部分，存放结点值C．只有一部分，存储表示结点间关系的指针D．分两部分，一部分存放结点值，另一部分存放结点所占单元数（）3．对于顺序存储的线性表，访问结点和删除结点的时间复杂度为（）。

A．O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1) （）4．设有4个数据元素a1、a2、a3和a4，对他们进行队操作，在进队操作时，按a1、a2、a3、a4次序每次进入一个元素。

假设队的初始状态是空，进队两次，出队一次，再进队两次，出队一次；这时，第一次出队得到的元素是（）A．a1 B. a2 C. a3 D. a4（）5．有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（）。

A.10B. 66C. 18000D. 33 （）6．串的长度是指（）A．串中所含不同字母的个数 B．串中所含字符的个数C．串中所含不同字符的个数 D．串中所含非空格字符的个数（）7．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。

与森林F对应的二叉树根结点的右子树上的结点个数是（）。

A．M1 B．M1+M2 C．M3 D．M2+M3（）8．用邻接表表示图进行广度优先遍历时，通常是采用来实现算法的。

A．栈 B. 队列 C. 树 D. 图（）9．在表长为ｎ的链表中进行线性查找，它的平均查找长度为A. ＡＳＬ＝ｎ;B. ＡＳＬ＝（ｎ＋１）／２;C. ＡＳＬ＝n＋１;D. ＡＳＬ≈ｌｏｇ２（ｎ＋１）－１（）10．下列关键字序列中，（）是堆。

安徽财经大学信息工程学院二00六年九月教案专用页内容（标题） 第1章 绪论 课时 2课时教学目的及要求教学目的: 介绍数据结构中常用的基本概念和术语以及学习数据结构的意义。

⑴基本概念和术语； ⑵学习数据结构的意义； ⑶算法的描述和分析。

教学要求： 了解本章介绍的各种基本概念和术语，掌握算法描述和分析的方法。

重点难点及其处理重点： ⑴数据结构的基本概念和术语， ⑵了解数据结构的逻辑结构、存储结构及数据的运算三方面的概念及相互关系， ⑶算法描述和算法分析的方法，对于一般算法能分析出时间复杂度。

难点： 算法复杂度的分析方法。

算法、算法的时间复杂度和空间复杂度、最坏的和平均的时间复杂度等概念。

算法的时间复杂度不仅仅依赖于问题的规模，也取决于输入实例的初始状态。

处理： 通过对一些已学习过的数据类型进行分析，由此引申出数据结构的概念。

通过一些算法举例，来说明具体的算法如何分析时间复杂度。

教学方法课堂讲授与课下作业相结合。

参考文献 1．朱若愚.数据结构（第二版）.北京：电子工业出版社，2001 2．张绍民.数据结构教程（C 语言版）.北京：中国电力出版社，2002教案专用页内容（标题）第2章线性表2.1 线性表的逻辑结构2.2 线性表的顺序存储结构课时2课时教学目的及要求教学目的：介绍线性表的逻辑结构和顺序存储表示方法，以及定义在逻辑结构上的各种基本运算及其在顺序存储结构上如何实现这些基本运算。

教学要求：在熟悉顺序存储结构的基础上，能够针对具体应用问题的要求和性质，选择合适的存储结构设计出相应的有效算法，解决与线性表相关的实际问题。

重点难点及其处理重点：⑴线性表的逻辑结构。

⑵线性表的逻辑结构特征。

⑶线性表上定义的基本运算，并能利用基本运算构造出较复杂的运算。

⑷顺序表的含义及特点，即顺序表如何反映线性表中元素之间的逻辑关系。

⑸顺序表上的插入、删除操作及其平均时间性能分析。

难点：⑴顺序表上实现的各种基本算法及相关的时间性能分析⑵利用顺序表设计算法解决筒单的应用问题。

2006/2007 学年 第 2 学期课程名称：数据结构 共 8 页 试卷： A 考试形式： 闭 卷一、单项选择题 (共10小题，每小题2分，共20分) 1．设某数据结构的二元组形式表示为A=(D ，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，则数据结构A 是（ ）。

(A) 线性结构 (B) 树型结构(C) 物理结构 (D) 图型结构2．设一维数组中有n 个数组元素，则读取第i 个数组元素的平均时间复杂度为（ ）。

(A) O(n) (B) O(nlog 2n) (C) O(1) (D) O(n 2) 3．设指针变量front 表示链式队列的队头指针，指针变量rear 表示链式队列的队尾指针，指针变量s 指向将要入队列的结点X ，则入队列的操作序列为（ ）。

(A) front->next=s ； front=s ； (B) s->next=rear ； rear=s ； (C) rear->next=s ； rear=s ； (D) s->next=front ；4. 设哈夫曼树中的叶子结点总数为m ，若用二叉链表作为存储结构，则该哈夫曼树中总共有（ ）个空指针域。

(A) 2m-1 (B) 2m (C) 2m+1 (D) 4m5. n个顶点的带权无向连通图的最小生成树包含（）个顶点。

(A) n-1 (B) n (C) n/2 (D) n+16. 一个栈的输入序列为1，2，3，4，下面哪一个序列不可能是这个栈的输出序列？（）(A) 1，3，2，4 (B) 2，3，4，1(C) 4，3，1，2 (D) 3，4，2，17．设二叉排序树中有n个结点，则二叉排序树的平均查找长度为（）。