当前位置：文档之家 › 数据结构试题2012答案

数据结构试题2012答案

  • 格式：pdf
  • 大小：243.66 KB
  • 文档页数：8

下载文档原格式

  / 8

合集下载

2012年10月--2007年1月自考2331数据结构历年试题和答案

2012年10月--2007年1月自考2331数据结构历年试题和答案

全国2012年10月高等教育一、单项选择题(本大题共l5小题，每小题2分，共30分)1．一个算法的时间耗费的数量级称为该算法的( D ) D．时间复杂度2．顺序表便于( D ) D．按序号查找结点3．设带头结点的单循环链表的头指针为head，指针变量P指向尾结点的条件是( B ) B．p->next==head4．设以数组A[0..m-1]存放循环队列，front指向队头元素，rear指向队尾元素的下一个位置，则当前队列中的元素个数为( A ) A．(rear-front+m)％m5．下列关于顺序栈的叙述中，正确的是( A )A．入栈操作需要判断栈满，出栈操作需要判断栈空6．A是一个10×10的对称矩阵，若采用行优先的下三角压缩存储，第一个元素a0,0的存储地址为1，每个元素占一个存储单元，则a7,5的地址为( D ) D．347．树的后序遍历等价于该树对应二叉树的( C ) C．中序遍历8．使用二叉线索树的目的是便于( D ) D．查找一个结点的前趋和后继9．设无向图的顶点个数为n，则该图边的数目最多为( B) B．n(n-1)／2 10．可进行拓扑排序的图只能是（Ｃ）C．有向无环图11．下列排序方法中稳定的是（Ａ）A．直接插入排序12．下列序列不为．．堆的是（Ｃ）C．75,65,30,l5,25,4513．对线性表进行二分查找时，要求线性表必须是（Ｃ）C．顺序存储且按关键字有序14．分别用以下序列生成二叉排序树，其中三个序列生成的二叉排序树是相同的，不同．．的序列是（Ａ）A．(4,1,2,3,5)15．下列关于m阶B树的叙述中，错误．．的是（Ａ）A．每个结点至多有m个关键字二、填空题(本大题共10小题，每小题2分，共20分)16．数据元素之间的逻辑关系称为数据的__逻辑____结构。

17．在线性表中，表的长度定义为__数据元素的个数____。

18．用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1、2、3、4，为了得到1、3、4、2的出栈顺序，相应的S和X的操作序列为__ＳＸＳＳＸＳＸＸ____。

数据结构真题2012年10月

数据结构真题2012年10月

数据结构真题2012年10月(总分：100.00，做题时间：90分钟)一、单项选择题(总题数：15，分数：30.00)1.一个算法的时间耗费的数量级称为该算法的______（分数：2.00）A.效率B.难度C.可实现性D.时间复杂度√解析：[考点] 算法的时间复杂度的概念[解析] 一个算法的时间耗费的数量级称为该算法的时间复杂度。

2.顺序表便于______（分数：2.00）A.插入结点B.删除结点C.按值查找结点D.按序号查找结点√解析：[考点] 顺序表的特征[解析] 顺序表便于按序号查找结点。

3.设带头结点的单循环链表的头指针为head，指针变量P指向尾结点的条件是______（分数：2.00）A.p-＞next-＞next==headB.p-＞next==head √C.p-＞next-＞next==NULLD.p-＞next==NULL解析：[考点] 指针变量p指向尾结点的判定条件[解析] 单循环链表的指针变量p指向尾结点的判定条件是p-＞next==head。

4.设以数组A[0..m-1]存放循环队列，front指向队头元素，rear指向队尾元素的下一个位置，则当前队列中的元素个数为______（分数：2.00）A.(rear-front+m)%m √B.rear-front+1C.(front-rear+m)%mD.(rear-front)%m解析：[考点] 队列中元素个数的计算[解析] 队列中元素的个数为(rear-front+m)%m5.下列关于顺序栈的叙述中，正确的是______（分数：2.00）A.入栈操作需要判断栈满，出栈操作需要判断栈空√B.入栈操作不需要判断栈满，出栈操作需要判断栈空C.入栈操作需要判断栈满，出栈操作不需要判断栈空D.入栈操作不需要判断栈满，出栈操作不需要判断栈空解析：[考点] 顺序栈的性质的判断[解析] 入栈操作需要判断栈满，出栈操作需要判断栈空。

6.A是一个10×10的对称矩阵，若采用行优先的下三角压缩存储，第一个元素a 0，0的存储地址为1，每个元素占一个存储单元，则a 7，5的地址为______（分数：2.00）A.25B.26C.33D.34 √解析：[考点] 对称矩阵的元素的地址的计算[解析] 若对称矩阵采用下三角压缩存储，根据其地址的计算公式，可得到所求元素的地址。

2012年数据结构期末考试题及答案

2012年数据结构期末考试题及答案

2012年数据结构期末考试题及答案一、选择题1．在数据结构中，从逻辑上可以把数据结构分为C。

A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．内部结构和外部结构2．数据结构在计算机内存中的表示是指A。

A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系3．在数据结构中，与所使用的计算机无关的是数据的A结构。

A．逻辑B．存储C．逻辑和存储D．物理4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储C。

A．数据的处理方法B．数据元素的类型C．数据元素之间的关系D．数据的存储方法5．在决定选取何种存储结构时，一般不考虑A。

A．各结点的值如何B．结点个数的多少C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。

6．以下说法正确的是D。

A．数据项是数据的基本单位B．数据元素是数据的最小单位C．数据结构是带结构的数据项的集合D．一些表面上很不相同的数据可以有相同的逻辑结构7．算法分析的目的是C，算法分析的两个主要方面是A。

（1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改进C．分析算法的易读性和文档性（2）A．空间复杂度和时间复杂度B．正确性和简明性C．可读性和文档性D．数据复杂性和程序复杂性8．下面程序段的时间复杂度是O（n2）。

s ＝0；for（I ＝0；i＜n；i＋＋）for（j＝0；j＜n；j＋＋）s ＋＝B[i][j]；sum ＝s ；9．下面程序段的时间复杂度是O（n*m）。

for（i ＝0；i＜n；i＋＋）for（j＝0；j＜m；j＋＋）A[i][j] ＝0；10．下面程序段的时间复杂度是O（log3n）。

i ＝0；while（i＜＝n）i ＝i * 3；11．在以下的叙述中，正确的是B。

A．线性表的顺序存储结构优于链表存储结构B．二维数组是其数据元素为线性表的线性表C．栈的操作方式是先进先出D．队列的操作方式是先进后出12．通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 B 。

《数据结构》期末考试题及答案

《数据结构》期末考试题及答案

2011-2012学年第一学期期末考查《数据结构》试卷（答案一律写在答题纸上，在本试卷上做答无效）一、选择（每题1分，共10分）1.长度为n的线性表采用顺序存储结构，一个在其第i个位置插入新元素的算法时间复杂度为（D）A.O(0)B.O(1)C.O(n)D.O(n2)2.六个元素按照6，5，4，3，2，1的顺序入栈，下列哪一个是合法的出栈序列？（D）A.543612B.453126C.346512D.2341563.设树的度为4，其中度为1、2、3、4的结点个数分别是4、2、1、2，则树中叶子个数为（B ）A.8B.9C.10D.114.设森林F对应的二叉树B有m个结点，B的右子树结点个数为n，森林F中第一棵树的结点个数是（ B ）A. m-nB.m-n-1C.n+1D.m+n5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（B）A.9B.11C.15D.不确定6.下列哪一个方法可以判断出一个有向图是否有环。

（A）A.深度优先遍历B.拓扑排序C.求最短路径D.求关键路径7.第7层有10个叶子结点的完全二叉树不可能有（B ）个结点。

A.73B.234C.235D.2368.分别用以下序列构造二叉排序树，与用其他三个序列构造的结果不同的是（B）A.（100,80,90,60,120,110,130）B.（100, 120, 110,130,80, 60,90）C.（100,60,80,90,120,110,130）D.（100,80, 60,90, 120, 130,110）9.对一组数据（84，47，25，15，21）排序，数据的排列次序在排序过程中变化如下：（1）84 47 25 15 21 （2）15 47 2584 21 （3）15 21 25 84 47（4）15 21 25 47 84则采用的排序方法是（B ）A.选择排序B.起泡排序C.快速排序D.插入排序10.对线性表进行折半查找时，要求线性表必须（D）A.以顺序方式存储B.以顺序方式存储，且数据元素有序C.以链接方式存储D.以链接方式存储，且数据元素有序二、填空（每空1分，共15分）1.数据结构中评价算法的两个重要指标是时间复杂度、空间复杂度。

(完整)数据结构考试题及答案资料,推荐文档

(完整)数据结构考试题及答案资料,推荐文档

2012年数据结构期末考试题及答案一、选择题1．在数据结构中，从逻辑上可以把数据结构分为C。

A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．内部结构和外部结构2．数据结构在计算机内存中的表示是指A。

A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系3．在数据结构中，与所使用的计算机无关的是数据的A结构。

A．逻辑B．存储C．逻辑和存储D．物理4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储C。

A．数据的处理方法B．数据元素的类型C．数据元素之间的关系D．数据的存储方法5．在决定选取何种存储结构时，一般不考虑A。

A．各结点的值如何B．结点个数的多少C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。

6．以下说法正确的是D。

A．数据项是数据的基本单位B．数据元素是数据的最小单位C．数据结构是带结构的数据项的集合D．一些表面上很不相同的数据可以有相同的逻辑结构7．算法分析的目的是C，算法分析的两个主要方面是A。

（1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改进C．分析算法的易读性和文档性（2）A．空间复杂度和时间复杂度B．正确性和简明性C．可读性和文档性D．数据复杂性和程序复杂性8．下面程序段的时间复杂度是O（n2）。

s ＝0；for（I ＝0；i＜n；i＋＋）for（j＝0；j＜n；j＋＋）s ＋＝B[i][j]；sum ＝s ；9．下面程序段的时间复杂度是O（n*m）。

for（i ＝0；i＜n；i＋＋）for（j＝0；j＜m；j＋＋）A[i][j] ＝0；10．下面程序段的时间复杂度是O（log3n）。

i ＝0；while（i＜＝n）i ＝i * 3；11．在以下的叙述中，正确的是B。

A．线性表的顺序存储结构优于链表存储结构B．二维数组是其数据元素为线性表的线性表C．栈的操作方式是先进先出D．队列的操作方式是先进后出12．通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着B 。

2012年江苏省数据结构试题集(10套题并附带答案)考资料

2012年江苏省数据结构试题集(10套题并附带答案)考资料
C．在单链表第一个元素前插入一个新元素
D．在单链表最后一个元素后插入一个新元素
4、数据结构中，从逻辑上可以把数据结构分成(?)。
?A．动态结构和静态结构?B．紧凑结构和非紧凑结构?C．线性结构和非线性结构?D．内部结构和外部结构
5、有向图采用邻接矩阵存储，某一行中非零元素的个数等于
A．对应顶点v的度
A．O（1） B．O（n） C．O（n2） D．O（nlog2n）
18、若一个栈以数组V[0．．n-1]存储，初始栈顶指针top为n，则x入栈的正确操作是
A．top=top+1；V[top]=x B．V[top]=x；top=top+1
C．top=top一1；V[mp]=x D．V[top]=x；top=top—l
19、下述排序方法中，时间性能和待排序记录的初始状态无关的是（ ）
A 插入排序和快速排序 B 归并排序和快速排序
C 选择排序和归并排序 D 插入排序和归并排序
20、与单链表相比，双链表的优点之一是 D 。
A．插入、删除操作更简单
A．各结点的值如何 B．结点个数的多少
C．对数据有哪些运算 D．所用的编程语言实现这种结构是否方便。
13、有向图采用邻接矩阵存储，某一行中非零元素的个数等于
A．对应顶点v的度
B．对应顶点v的出度
C．对应顶点v的入度
D．依附于对应顶点v的边数
14、与单链表相比，双链表的优点之一是 D 。
47、与单链表相比，双链表的优点之一是 D 。
A．插入、删除操作更简单
B．可以进行随机访问
C．可以省略表头指针或表尾指针
D．顺序访问相邻结点更灵活

2012甘肃省JAVA版数据结构试题及答案

1、设有一个栈，元素的进栈次序为A, B, C, D, E,下列是不可能的出栈序列是（ C ）。

A） A, B, C, D, EB） B, C, D, E, AC） E, A, B, C, DD） E, D, C, B, A2、倘若在对串的插入、删除运算中，期望运算速度最快，则应采用（C ）。

A）顺序表示法 B）单字符为结点的单链表表示法C）等量分块表示法 D）不等量分块表示法3、设单链表中指针p指向结点m，若要删除m之后的结点（若存在），则需修改指针的操作为（ A ）。

A）p->next=p->next->next; B） p=p->next;C）p=p->next->next; D） p->next=p;4、线性表的链接实现有利于（ A ）运算。

A）插入 B）读元素C）查找 D）定位5、二叉树第i(i≥1)层上至多有（ C ）结点。

A）2i B）2i C）2i-1 D）2i-16、串的逻辑结构与（ D ）的逻辑结构不同。

A）线性表 B）栈C）队列 D）树7、下列序列中，执行第一趟快速排序后得到的序列是（ 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]8、如果结点A有3个兄弟，而且B为A的双亲，则B的度为（ B ）。

A）3 B）4 C）5 D）19、有一个有序表{1，4，6，10，18，35，42，53，67，71，78，84，92，99}。

当用二分查找法查找键值为84的结点时，经（ B ）比较后查找成功。

A) 4 B)3 C)2 D)1210、在一个链队列中，假定front和rear分别为队首和队尾指针，则插入一个结点的操作为（ B ）。

A）front=front->next; B） rear=rear->next;C） rear=front->next; D） front=rear->next ;11、以下属于顺序存储结构优点的是（ A ）。

02142数据结构导论份真题及答案.doc

2012年10月高等教育自学考试全国统一命题考试数据结构导论试题课程代码：02142请考生按规定用笔将所有试题的答案涂、写在答题纸上。

选择题部分注意事项：1. 答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。

2. 每小题选出答案后，用2B铅笔把答题纸上对应题目的答案标号涂黑。

如需改动，用橡皮擦干净后，再选涂其他答案标号。

不能答在试题卷上。

一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的。

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

1.下面几种算法时间复杂度阶数中，值最大的是A.O(nlog2n)B.O(n2)C.O(n)D.O(2n)2.即使输入非法数据，算法也能适当地做出反应或进行处理，不会产生预料不到的运行结果，这种算法好坏的评价因素称为A.正确性B.易读性C.健壮性D.时空性3.设顺序表的长度为100，则在第40个元素之后插入一个元素所需移动元素的个数为A.40B.60C.61D.1004.设带头结点的单循环链表的头指针为head，则判断该链表是否为空的条件是A. head->next==headB. head->next==NULLC. head!=NULLD. head==NULL5.在链栈的运算中，不需要．．．判断栈是否为空的是A.出栈B.进栈C.取栈顶元素D.求链栈的元素个数6.一个队列的输入序列是A，B，C，D，则该队列的输出序列是A.A，B，C，DB.B，C，D，AC.D，C，B，AD.C，D，B，A7.以行序为主序的二维数组a［3］［5］中，第一个元素a［0］［0］的存储地址是100，每个元素占2个存储单元，则a［1］［2］的存储地址是A.100B.108C.114D.1168.对任何一棵二叉树T，若叶结点数为5个，则度为2的结点个数为A.4B.5C.6D.无法确定9.m个叶结点的哈夫曼树中，其结点总数为A.mB.2m+1C.2mD.2m-110.二叉树的中序遍历序列中，结点P排在结点Q之前的条件是A.在二叉树中P在Q的左边B.在二叉树中P在Q的右边C.在二叉树中P是Q的祖先D.在二叉树中P是Q的子孙11.有10个顶点的无向完全图的边数是A.11B.45C.55D.9012.在带权有向图中求两个结点之间的最短路径可以采用的算法是A.迪杰斯特拉（Dijkstra）算法B.克鲁斯卡尔（Kruskal）算法C.普里姆（Prim）算法D.深度优先搜索（DFS）算法13.二分查找（Binary Search）算法的时间复杂度是A.O（n2）B.O（nlog2n）C.O（n）D.O（log2n）14.在一棵初始时为空的二叉树中，依次插入键值序列50，72，43，85，75，20，38，45，65，60，构造对应的二叉排序树以后，查找元素60要进行的比较次数是A.2B.3C.4D.515.快速排序属于A.插入排序B.交换排序C.选择排序D.归并排序非选择题部分注意事项：用黑色字迹的签字笔或钢笔将答案写在答题纸上，不能答在试题卷上。

数据结构,期末考试试卷,复旦大学计算机科学技术学院-2012

2
7、 分析对比 AVL 树和 Hash 的时空特性，并讨论它们的适合场合。(6 分)
第 7 页
时空特性： AVL 树是高度平衡的二叉查找树，查找时间复杂度为 O(logn)，Hash 的查找时间复杂度为 O(1)。 存储开销 Hash 往往比 AVL 树小。 适合场合： Hash 必须处理冲突，而 AVL 树不存在这种问题。对于删除操作，AVL 树的时间开销很稳定，为 O(logn)，而 Hash，如果采用拉链法处理冲突，则删除操作易于实现，如果采用开放定址法，则 删除操作很难实现，因此开放定址法的 Hash 不适合更新频繁的数据存储。另外，AVL 树对数据 的存储是有序的，而 Hash 对数据的存储并不能反映数据之间的大小关系。因此，AVL 树适用于 有序的数据存储，而 Hash 适用于数据量比较大且分布比较均匀，对数据排序无要求的数据存储。
专业
题号 得分
学号
一 二 三
姓名
四 总分
成绩
一、填空题（25%,1~8 题每题 2 分）
（ 装 订 线 内 不 要 答 题 ） 1、 设 W 为一个二维数组，其每个数据元素占用 4 个字节，行下标 i 从 0 到 7 ，列下标 j 从 0 到 3 ，则二维数组 W 的数据元素共占用 个字节。若按行顺序存放二维数组 W，其起 始地址为 100(10 进制)，则二维数组元素 W[6，3]的起始地址为 （10 进制表示） 。 答：128, 208。 2、 后缀算式 9 2 3 + - 10 2 / - 的值为__________。中缀算式（3+4X）-2Y/3 对应的后缀算 式为_______________________________。 答：-1, 3 4 X * + 2 Y * 3 / -。

《数据结构》习题及答案：第2章 线性表(第1次更新2012-3)

第2章线性表一、选择题1.表长为N 的顺序表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均次数为（），删除一个元素需要移动的元素个数为（）。

【＊＊，★】A. (N-1)/2B. NC. N+1D. N-1E. N/2F. (N+1)/2G. (N-2)/22.线性表是具有N 个（）的有限序列。

【＊】A、表元素B、字符C、数据元素D、数据项E、信息3.“线性表的逻辑顺序和物理顺序总是一致的。

”这个结论是（）。

【＊】A、正确的B、错误的C、不一定，与具体结构有关。

4.线性表采用链式存储结构时，要求内存中可用存储单元的地址（）。

【＊，★】A、必须是连续的B、部分地址必须是连续的C、一定是不连续的D、连续或不连续都可以。

5.带头结点的单链表为空的判定条件是（）。

【＊】A、head==NULLB、head->next==NULLC、head->next==headD、head!=NULL6.不带头结点的单链表head 为空的判定条件是（）。

【＊】A、head==NULLB、head->next==NULLC、head->next==headD、head!=NULL7.非空的循环单链表head 的尾结点P 满足（）。

（注:带头结点）【＊】A、P->NEXT=NULLB、p=NULLC、p->next==headD、p==head8.在一个具有n 个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（）。

【＊，★】A、O(1)B、O(n)C、O(n2)D、O(nlog2n)9.在一个单链表中，若删除P 所指结点的后继结点，则执行（）。

【＊，★】A、p->next=p->next->nextB、p=p->next;p->next=p->next->nextC、p->next=p->next;D、p=p->next->next;10.在一个单链表中，若在Ｐ所指结点之后插入Ｓ所指结点，则执行（）。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

答案：O(n)、O(1)、O(1) 5．取出广义表 A=((a, x, y, z), (b, c)中的原于 c 的 Tail()和 Head()组成的复合函数是： __________________。 答案：Head(Tail(Head(Tail(A)))) 6. 已知完全二叉树的第 6 层有 4 个结点，则其叶子结点数是_______________. 答案：18 个 7. 在一个有向图中，所有顶点入度之和等于所有顶点出度之和的_____倍。 答案：1 8. 对两棵具有相同关键字集合而形状不同的二义排序树，____________遍历它们得到 的序列的顺序是一样的。 答案：中序 9. 设表中元素的初始状态是按键值递增的，分别用堆排序、快速排序、冒泡排序和 归并排序方法对其仍按递增顺序进行排序，则_____________最省时间，___________ 最费时间。 答案：冒泡排序、快速排序
第 1 页 共 8 页
第 2 页 共 8 页
C．任一结点无左孩子 D．任一结点无右孩子 9. 采用哈希技术实现表的存储和查找，需解决的主要问题是( D ) A．如何申请到足够大的空间 B．如何正确认识元素之间的逻辑关系 C．如何找到一个好的查找方法 D．如何构造一个散列地址均匀分布的哈希函数 10. 表 A 中有 1000 个元素，如果要求求出其中最大的 10 个元素，则采用( A )排序方 法最省时间。 A．堆排序 B．希尔排序 C．快速排序 D．直接选择排序 11. 设连通图 G 的顶点数为 n，则 G 的生成树的边数为( B )。 A．n B．n­1 C．2n D．2n­1 12. 若在线性表中采用折半查找法查找元素。该线性表应该是( C ) A 元素按值有序 B．采用顺序存储结构 C. 元素按值有序，且采用顺序存储结构 D. 元素按值有序，且采用链式存储结构 13. 在待排序文件已基本有序的前提下，下述排序方法中效率最高的是( A ) A. 直接插入排序 B. 直接选择排序 C. 快速排序 D. 归并排序 14. 无向图中一个顶点的度是指图中( B )。 A. 通过该顶点的简单路径数 B．与该顶点相邻接的顶点数 C．通过该顶点的回路数 D．与该顶点连通的顶点数 15．在下列排序方法中，平均时间性能为 O(nlogn)且空间性能最好的是( B )。 A. 快速排序 B．堆排序 C．归并排序 D．基数排序
4. 从空树起，依次插入关键字 40、8、90、15、62、95、12、23、56、32，构造一课二 叉排序树。 (1)画出该二叉排序树。 (2)画出删去该树中元素值为 90 的结点之后的二叉排序树。
­­­5 分
­­5 分
5. 巳知—个文件的初始关键字序列为：265 301 751 129 937 863 742 694 76 438。写出建成大顶堆后的序列和第一次堆排序后重建大顶堆的序列。 初始大顶堆： 973 694 863 265 438 751 742 129 76 301 ­­3 分 第一次堆排序后重建大顶堆：863 694 751 265 438 301 742 129 76 ­­3 分
二、填空题（9 小题，每空 1 分，共 15 分）
1 ． 当 一 个 线 性 表 经 常 进 行 存 取 操 作 而 很 少 进 行 插 入 和 删 除 操 作 时 ， 则 采 用 _______________存储结构为宜，相反，当经常进行的是插入和删除操作时．则采用 _____________存储结构为 答案 顺序、链式 2. 当向一个顺序表插入一个元素时，从插入位置开始向后的所有元索均________一个 位置，移动过程是从_______向_________依次移动每一个入素。 答案：后移、后、前 3. 已知一个栈的输入序列为 1，2，3，…，n ，则其输出序列的第 2 个元素力 n 的输出 序列的种数是________。 答案：n­1 4. 用循环链表表示的队列长度为 n，若只设头指针，则出队和入队的时间复杂度分别是 O(1) 和 __________ ；若只设尾指针，则出队和人队的时间复杂度分别是 ________ 和 ___________。
第 3 页 共 8 页
第 4 页 共 8 页
2 a1 1 a2 a3 3
a4
4 a8 a7 a9 5 6
a5 a6
答： ve(1)=0 ve(2)=max(a1,a2+a3)=3+3=6 ve(3)=3 ve(4)= max(6+a4,3+a5)=3+9=12 ve(5)=12+6=18 ve(6)=18+3=21 ­­­2 分 vl(6)=ve(6)=21 vl(5)=21­3=18 vl(4)=18­6=12 vl(3)=12­9=3 vl(2)=12­5=7 vl(1)=3­3=0 ­­­2 分 e(a1)=ve(1)=0 e(a2)=0 e(a3)=ve(3)=3 e(a4)=ve(2)=6 e(a5)=ve(3)=3 e(a6)=ve(3)=3 e(a7)=ve(4)=12 e(a8)=ve(4)=12 e(a9)=ve(5)=18 ­­­2 分 l(a9)=vl(6)­a9=21­3=18 l(a8)=21­2=19 l(a7)=vl(5)­a7=18­6=12 l(a6)=vl(5)­a6=18­4=14 l(a5)=vl(4)­a5=12­9=3 l(a4)=vl(4)­a4=12­5=7 l(a3)=vl(2)­a3=7­3=4 l(a2)=vl(3)­a2=3­3=0 l(a1)=vl(2)­a1=7­2=5 ­­­2 分 1 ve vl 0 0 2 6 7 3 3 3 4 12 12 5 18 18 6 21 21
四、算法题（3 小题，共 15 分）
1. 设计一个实现下述要求的 Locate 运算的算法：有—个双向链表，每个结点 node 有四 个域，prior、next、data 和 freq。初始化时，freq 域的值都为 0，每当在链表中进行一次 Locate (s，x)运算时,令元素值为 x 的节点中 freq 域的值增加 1，并使此链表中结点保持 按访问频度递减的顺序排列，以便使频繁访问的结点总是靠近表头。 (8 分) DuLinkList Locate(DuLinkList s, ElemType x) DuLinkList p,q; p=s­>next;
第 5 页 共 8 页
第 6 页 共 8 页
while(p!=s &&p­>data!=x) p=p­>next; if(p==s) return NULL; p­>freq++; q=p­>prior; /*向前查找*/ while(q!=s && q­>freq<p­>freq) q=q­>prior; if (q!=p­>prior) { p­>prior­>next=p­>next； p­>next­>prior=p­>prior; p­>next=q­>next; q­>next­>prior=p; q­>next=p; p­>prior=q; } return p; } 2. 编写算法 find，使 find 可以求出指定结点在给定的二叉排序树中所在的层数。 typedef struct BiTNode{ /*记录类型*/ KeyType key; /*关键字项*/ struct BiTNode *lchild,*rchild; /*左右孩子指针*/ } BiTNode, *BiTree; int find(BiTree T, BiTNode *p) { if (p==NULL) return 0; int layer=1; while (T!=NULL) { if (p==T) return layer; if (p­>key<T­>key) T=T­>lchild; else T=T­>rchild; layer++; } return 0; }
三、简答题（5 小题，共 40 分）
1．用深度优先搜索遍历下图所示的无向阁，试给出以 A 为起点的顶点访问序列(同一 个顶点的多个邻点，按字母顺序访问)，并给出一棵最小生成树。 (8 分)
顶点访问序列：A B E D H I F C G J 最小生成树：
­­­­3 分
­­­­5 分 2． 计算下图所示的 AOE 网中各顶点所表示的事件发生时间 ve(j)、v1(j)，所表示活动 的开始时间 e(i)，l(i)，并找出其关键路径。 其中： a1＝2， a2＝3， a3=3， a4=5， a 5＝9， a6＝4， a7＝6． a8=2， a9＝3。
a1 a2 a3 a4 a5 a6 a7 a8 a9 e 0 l 5 0 0 3 4 6 7 3 3 3 12 12 18 14 12 19 18
所以，图中关键路径为 a2、a5、a7、a9，即(v1、v3、v4、v5、v6) ­­­2 分 3. 一棵二叉树由 A、B、C、D、E、F、I、J、K 九个结点构成，其先序、中序和后序遍 历序列分别如下，具中一部分未标出，请构造出该二叉树。 （6 分） 先序：AC D EGH K 中序：C B FA 科 技 大 学
考试时间 120 分钟
试
题号 分数
1.考试形式：闭卷；2。考试日期：2012 年
题（A）
五 六 七 八 九 十 总分
月 日 3.本试卷共 四 大题，满分 100 分。
一
二
三
四
班级
学号
姓名
任课教师
一、单选题（15 小题，每题 2 分，共 30 分）
数据结构中，从逻辑上可以把数据结构分成( C )。 A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．内部结构和外部结构 2. 在单链表中，指针 p 指向元素为 x 的节点，实现“删除 x 的后继”的语句是( B )。 A．p=p­>next B．p­>next= p­>next­>next C．p­>next =p D．p= p­>next­>next 3. 与线性表的链接存储不相符的特性是( B )。 A. 插入和删除操作灵活 B．需连续的存储空间 C．存储空间动态分配 D．需另外开辟空间来保存元素问的关系关于线性表 4. 设一个栈的输入序列为 A、 B 、 C 、 D ， 则借助一个栈所得到的输出序列不可能是( D )。 A．A，B，C，D B．D，C，B，A C．A，C，D，B D．D，A，B，C 5. 当利用大小为 n 的数组顺序存储一个栈时，假定用 top＝＝n 表示栈空，则向这个栈 插入一个元素时，首先应执行( B )语句修改 top 指针。 A．top++ B．top­­ C．top=0 D．top 6．链栈与顺序栈相比，比较明显的优点是( D ) A．插入操作更加方便 B．删除操作更加方便 C．不会出现下溢的情况 D．不会出现上溢的情况 7. 将一个 A[100][100]的三对角矩阵，按行优先存人一维数组 B[298] 中，A 中的元素 A[65][64]在 B 中的位置 K 为( B )。 A. 198 B．194 C. 197 D．199 8. 某二叉树的先序序列和后序序列正好相同，则该二叉树一定是( A )的二叉树 A．空或只有一个结点 B．高度等于其结点数 1.