厦门理工学院12级数据结构期末试卷与答案

《数据结构》期末考试试题及答案一、单项选择题1. 数据结构是计算机科学的基础学科之一。

下列哪个选项正确描述了数据结构的定义？A. 数据结构是一种计算机程序B. 数据结构是一种存储和组织数据的方法C. 数据结构是一种人工智能技术D. 数据结构是一种操作系统答案：B2. 链表和数组是常见的数据结构，它们之间的主要区别是：A. 数组可以存储不同类型的数据，而链表只能存储相同类型的数据B. 数组的元素在内存中是连续存储的，而链表的元素在内存中是分散存储的C. 链表可以随机访问元素，而数组只能顺序访问元素D. 链表的插入和删除操作更高效，而数组的访问操作更高效答案：B3. 在二叉树中，每个节点最多可以有多少个子节点？A. 1B. 2C. 3D. 无限多个答案：B二、填空题1. 假设有一组数据 [5, 8, 3, 2, 9]，按照从小到大的顺序进行冒泡排序的过程中，经过三次交换后的结果是__2__，__3__，__5__，__8__，__9__。

2. 请完成以下代码，实现栈的入栈和出栈操作：```pythonclass Stack:def __init__(self):self.stack = []def push(self, item):self.stack.append(item)def pop(self):if not self.is_empty():return self.stack.pop()def is_empty(self):# 示例代码s = Stack()s.push(1)s.push(2)s.push(3)print(s.pop()) # 输出 3print(s.pop()) # 输出 2print(s.is_empty()) # 输出 False ```答案：```pythonclass Stack:def __init__(self):self.stack = []def push(self, item):self.stack.append(item)def pop(self):if not self.is_empty():def is_empty(self):return len(self.stack) == 0# 示例代码s = Stack()s.push(1)s.push(2)s.push(3)print(s.pop()) # 输出 3print(s.pop()) # 输出 2print(s.is_empty()) # 输出 False```三、简答题1. 请简要介绍树的基本概念及常见的树结构。

数据结构期末考试试题及答案一、选择题1. 以下哪种数据结构是线性存储结构？A. 树B. 图C. 栈D. 队列答案：C2. 在链表中，如果一个节点既没有前驱也没有后继，那么这个节点被称作什么？A. 首节点B. 尾节点C. 中间节点D. 孤立节点答案：B3. 树的度是指什么？A. 树中节点的个数B. 树中最大的层次数C. 树的分支数D. 树的节点的度的最大值答案：C4. 在二叉搜索树中，若要查找给定值的节点，当查找失败时应返回的值是？A. -1B. 0C. 1D. 该值本身答案：A5. 快速排序算法的时间复杂度最坏情况下是多少？A. O(n)B. O(nlogn)C. O(n^2)D. O(n!)答案：C二、填空题1. 在顺序表中，元素的物理位置相邻的特点是________，这使得顺序表在________操作上具有较高的效率。

答案：连续性；访问2. 链表相比顺序表的优势在于它能够动态地________存储空间，并且________操作不需要移动大量元素。

答案：分配和释放；插入与删除3. 栈是一种________的数据结构，只允许在________进行插入和删除操作。

答案：后进先出；栈顶4. 图的遍历算法主要有两种，分别是________和________。

答案：深度优先搜索；广度优先搜索5. 哈夫曼树是一种特殊的二叉树，它常用于数据压缩，其构建过程是基于________原则。

答案：最小权值三、简答题1. 请简述数组和链表的优缺点。

答案：数组通过索引直接访问元素，访问速度快，但大小固定，插入和删除操作需要移动大量元素。

链表元素通过指针连接，可以动态分配大小，插入和删除效率高，但访问速度较慢，因为需要从头开始遍历。

2. 什么是二叉树的前序遍历、中序遍历和后序遍历？答案：二叉树的前序遍历是先访问根节点，然后遍历左子树，最后遍历右子树。

中序遍历是先遍历左子树，然后访问根节点，最后遍历右子树。

后序遍历是先遍历左子树，然后遍历右子树，最后访问根节点。

2020-2021学年《数据结构》期末考试复习试题一、单项选择题1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（）。

(A)、正确性(B). 可行性(C). 健壮性(D). 输入性2．设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（）。

for(i=n-1；i>=0；i--)for(j=0；j<i；j++) S；(A)、n2(B). O(nlgn) (C). O(n) (D). O(n2)3．折半查找法适用于（）。

（A）、有序顺序表（B）、有序单链表（C）、有序顺序表和有序单链表都可以（D）、无限制4．顺序存储结构的优势是（）。

（A）、利于插入操作（B）、利于删除操作（C）、利于顺序访问（D）、利于随机访问5．深度为k的完全二叉树，其叶子结点必在第（）层上。

（A）、k-1 （B）、k （C）、k-1和k （D）、1至k6．具有60个结点的二叉树，其叶子结点有12个，则度过1的结点数为（）（A）、11 （B）、13 （C）、48 （D）、377．图的Depth-First Search(DFS)遍历思想实际上是二叉树（）遍历方法的推广。

（A）、先序（B）、中序（C）、后序（D）、层序8．在下列链队列Q中，元素a出队的操作序列为（）（A）、p=Q.front->next; p->next= Q.front->next;（B）、p=Q.front->next; Q.front->next=p->next;（C）、p=Q.rear->next; p->next= Q.rear->next;（D）、p=Q->next; Q->next=p->next;9． Huffman树的带权路径长度WPL等于（）（A）、除根结点之外的所有结点权值之和（B）、所有结点权值之和（C）、各叶子结点的带权路径长度之和（D）、根结点的值10．线索二叉链表是利用（）域存储后继结点的地址。

数据结构期末考试试题及答案一、选择题1. 评价一个算法时间性能的主要标准是( )。

A、算法易于调试B、算法易于理解C、算法的稳定性和正确性D、算法的时间复杂度2. 计算机算法具备有输入、输出、（）等五个特性。

A、可行性、可移植性和可扩充性B、可行性、确定性和有穷性C、确定性、有穷性和稳定性D、易读性、稳定性和安全性3. 带头结点的单链表head为空的判定条件是（）。

A、head==NULLB、head->next==NULLC、head->next==headD、head！=NULL4. 以下关于线性表的说法不正确的是( )。

A、线性表中的数据元素可以是数字、字符、记录等不同类型。

B、线性表中包含的数据元素个数不是任意的。

C、线性表中的每个结点都有且只有一个直接前趋和直接后继。

D、存在这样的线性表：表中各结点都没有直接前趋和直接后继。

5. 在顺序表中，只要知道( )，就可在相同时间内求出任一结点的存储地址。

A、基地址B、结点大小C、向量大小D、基地址和结点大小6. ( )运算中，使用顺序表比链表好。

A、插入B、删除C、根据序号查找D、根据元素值查找7. 一个长度为n的顺序表中，向第i个元素之前插入一个新元素时，需要向后移动（）个元素A、n-iB、n-i+1C、n-i-1D、i8. ( )适合作为经常在首尾两端操作线性表的存储结构。

A、顺序表B、单链表C、循环链表D、双向链表9. 栈和队列的共同点是（）A、都是先进后出B、都是先进先出C、只允许在端点处插入和删除元素D、没有共同点10. 一个队列的入列序列是1 2 3 4，则队列的输出序列是( )。

A、4 3 2 1B、1 2 3 4C、1 4 3 2D、3 2 4 111. 队列与一般的线性表的区别在于( )。

A、数据元素的类型不同B、运算是否受限制C、数据元素的个数不同D、逻辑结构不同12. “假上溢”现象会出现在( )中。

A、循环队列B、队列C、链队列D、顺序队列二、填空题1．数据的逻辑结构被分为集合、线性结构、树形结构和图结构。

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

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

A.73B.234C.235D.2368.分别用以下序列构造二叉排序树，与用其他三个序列构造的结果不同的是（）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 25 84 21 （3）15 21 25 84 47（4）15 21 25 47 84则采用的排序方法是（）A.选择排序B.起泡排序C.快速排序D.插入排序10.对线性表进行折半查找时，要求线性表必须（）A.以顺序方式存储B.以顺序方式存储，且数据元素有序C.以链接方式存储D.以链接方式存储，且数据元素有序二、填空（每空1分，共15分）1.数据结构中评价算法的两个重要指标是、空间复杂度。

线 订 装数据结构与算法A卷答案12-13学年第一学期一、选择题：（本题共20小题，每题2分，共40分）1-5：AABDC 6-10：DDDBC 11-15：CBCDD 16-20：ABCAB二、分析运算题（本题共6小题，每题5分，共30 分）(1) 如果输入序列为1 2 3,先进入栈结构后进入队列结构，试写出所有的出队列序列。

输出序列1 2 3（1分）输出序列1 3 2（1分）输出序列2 1 3（1分）输出序列2 3 1（1分）输出序列3 2 1（1分）输出序列3 1 2（扣3分）(2) 假设一棵二叉树的前序(先序)遍历序列为ABDECF和中序序列为DBEAFC，画出二叉树并写出后序遍历序列。

①（3分）②后序遍历：DEBFCA （2分）(3) 用二叉树表示算术表达式如图1所示。

①按图画出对应的算术表达式②写出后序（后缀）表达式算术表达式：(a+b+c*(d+e)+f)*(g+h) （2分）后序表达式：ab+cde+*+f+gh+*（3分）(4) 请写出有向图2中顶点1-6的入度和出度1: 入度：3出度：02: 入度：2出度：23: 入度：1出度：24: 入度：1出度：35: 入度：2出度：16: 入度：2出度：3(入度2.5分，出度2.5分)(5) 给定一组项及其权值，假定项都存放于二叉树的树叶结点，则具有最小带权外部路径长度的树称为huffman(赫夫曼) 树。

给定项及相应的权如下表：画出相应的huffman树。

(5分)(6)已经邻接矩阵如图3所示，判断该图是有向图还是无向图，用顶点1-6画出该图。

有向图（2分）三、程序填空题（本题共5空，每空2分，共10分）(1)：p!=NULL(2)：p = p->next;(3): Q.front= =Q.rear(4): Q.front->next=p->next;(5): Q.rear=Qfront;四、算法设计题（本题共2小题，共20分）1、（10分）算法如下：void move(sqlist L){int i=0,j=L.lenght-1,k; 1分int temp;while(i<j) 1分{while(L.elem[i]<=0) i++; 2分while(L.elem[j]>=0) j--; 2分if(i<j) 1分{temp=L.elem[i];L.elem[i]=L.elem[j];L.elem[j]=temp; 3分}}}注：算法执行次数（时间）比给定算法更多，不得超过6分。

一、选择题。

(每小题2分，共40分)(1) 计算机识别.存储和加工处理的对象被统称为____A____。

A.数据B.数据元素C.数据结构D.数据类型(2) 数据结构通常是研究数据的____ A _____及它们之间的联系。

A.存储和逻辑结构B.存储和抽象C.理想和抽象D.理想与逻辑(3) 不是数据的逻辑结构是____ A ______。

A.散列结构B.线性结构C.树结构D.图结构(4) 数据结构被形式地定义为<D,R>,其中D是____ B _____的有限集，R是____ C _____的有限集。

A.算法B.数据元素C.数据操作D.逻辑结构(5) 组成数据的基本单位是____ A ______。

A.数据项B.数据类型C.数据元素D.数据变量(6) 设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构A是____ A ______。

A.线性结构B.树型结构C.图型结构D.集合(7) 数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为___ C ____。

A.存储结构B.逻辑结构C.顺序存储结构D.链式存储结构(8) 在数据结构的讨论中把数据结构从逻辑上分为___ A ____。

A.内部结构与外部结构B.静态结构与动态结构C.线性结构与非线性结构D.紧凑结构与非紧凑结构(9) 对一个算法的评价，不包括如下____ B _____方面的内容。

A.健壮性和可读性B.并行性C.正确性D.时空复杂度(10) 算法分析的两个方面是__ A ____。

A.空间复杂性和时间复杂性B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性(11) 线性表是具有n个___ C _____的有限序列（n≠0)。

A.表元素B.字符C.数据元素D.数据项(12) 线性表的存储结构是一种____ B ____的存储结构。

“数据结构”期末考试试题一、单选题(每小题2分,共12分）1．在一个单链表HL中，若要向表头插入一个由指针p指向的结点,则执行（ )。

A． HL＝ps p一>next＝HLB． p一>next＝HL；HL＝p3C． p一>next＝Hl；p＝HL；D． p一〉next＝HL一>next;HL一〉next＝p；2．n个顶点的强连通图中至少含有（ ).A。

n—l条有向边 B.n条有向边C.n(n—1)／2条有向边 D。

n（n一1）条有向边3。

从一棵二叉搜索树中查找一个元素时,其时间复杂度大致为（ )。

A。

O(1) B。

O（n）C.O(1Ogzn）D.O(n2）4．由权值分别为3，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）。

A．24 B．48C． 72 D． 535．当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最好把它说明为( )参数,以节省参数值的传输时间和存储参数的空间。

A.整形B.引用型C.指针型D.常值引用型·6．向一个长度为n的顺序表中插人一个新元素的平均时间复杂度为( ）。

A．O（n) B．O(1)C．O（n2） D．O（10g2n)二、填空题(每空1分，共28分)1．数据的存储结构被分为——、——、-—和—-四种。

2．在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为——域和——域。

3．-—中缀表达式 3十x＊(2。

4／5—6）所对应的后缀表达式为———-。

4．在一棵高度为h的3叉树中,最多含有——结点。

5．假定一棵二叉树的结点数为18，则它的最小深度为—-,最大深度为-—·6．在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定——该结点的值，右子树上所有结点的值一定-—该结点的值。

7．当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层—-调整，直到被调整到——位置为止.8．表示图的三种存储结构为——、——和-——.9．对用邻接矩阵表示的具有n个顶点和e条边的图进行任一种遍历时，其时间复杂度为-—，对用邻接表表示的图进行任一种遍历时，其时间复杂度为—-。

2013—2014学年第一学期闽江学院考试试卷《数据结构与算法》A 卷参考答案及评分标准一、选择题答案（每题2分） 30%二、填空题（每空 2分） 20% 1、p->nexts 2、53、1+n2+2n3+…+(k-1)nk4、n-1 n+15、CDBGFEA6、2n-17、A[7]、A[3]、A[5]、A[4] 8、2e三、判断题（每题1分） 10%四、应用题（5小题） 32 %1、（6分）画哈夫曼树（每个叶子结点位置正确得0.5分，总5分） 计算WPL 正确得1分WPL=(2+4)*5+(5+7+8)*4+(9+10+15+18)*3+22*2=30+80+156+44=3102、（8分）(1)二叉排序树 (每个结点在正确的位置正确得0.5分，总6分)(2)查找成功时的平均查找长度： （总2分） ASL=(1*1+2*2+4*3+5*4)/12 =37/12= 3.083、（5分）（每行正确得0.5分，总5分） 原始数据：（27），10，21，37，9，55，16，61，103，2 第一趟后:（10，27），21，37，9，55，16，61，103，2 第二趟后:（10，21，27），37，9，55，16，61，103，2 第三趟后:（10，21，27，37），9，55，16，61，103，2 第四趟后:（9，10，21，27，37），55，16，61，103，2第五趟后:（9，10，21，27，37，55），16，61，103，2 第六趟后:（9，10，16，21，27，37，55），61，103，2 第七趟后:（9，10，16，21，27，37，55，61），103，2 第八趟后:（9，10，16，21，27，37，55，61，103），2 第九趟后:（2，9，10，16，21，27，37，55，61，103） 4、（5分）哈希表，每个表结点在正确的位置得0.5分，计4分；查找成功时的平均查找长ASL 成功=（1*6+2*1+3*1）/8=11/8=1.3625 (1分) 5、（8分）得分标准：每个结点的邻接点均正确得0.5分（即每行0.5分）克鲁斯卡尔算法画出最小生成树的过程（4分）：（1） （2）（3）（4）（5）（6）（7）（8）得分标准：依次得出上面八张图，每张0.5分，计4分，其中第（4）、（5）张，第（6）、（7）张两权值相同的边顺序可调换。

单元练习9一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳）（√）（1）二分查找法要求待查表的关键字值必须有序。

（ㄨ）（2）对有序表而言采用二分查找总比采用顺序查找法速度快。

（ㄨ）（3）在二叉排序树中，根结点的值都小于孩子结点的值。

（√）（4）散列存储法的基本思想是由关键字的值决定数据的存储位置。

（√）（5）哈希表是一种将关键字转换为存储位置的存储方法。

（ㄨ）（6）选择好的哈希函数就可以避免冲突的发生。

（ㄨ）（7）在有序的顺序表和有序的链表上，均可以采用二分查找来提高查找速度。

（√）（8）采用分块查找，既能实现线性表所希望的查找速度，又能适应动态变化的需要。

（√）（9）哈希法的查找效率主要取决于哈希表构造时选取的哈希函数和处理冲突的方法。

（ㄨ）（10）在二叉排序树上删除一个结点时，不必移动其它结点，只要将该结点的父结点的相应的指针域置空即可。

二．填空题（1）顺序查找法，表中元素可以任意存放。

（2）在分块查找方法中，首先查找索引，然后再查找相应的块。

（3）顺序查找、二分查找、分块查找都属于静态查找。

（4）静态查找表所含元素个数在查找阶段是固定不变的。

（5）对于长度为n的线性表，若进行顺序查找，则时间复杂度为 O（n）。

（6）对于长度为n的线性表，若采用二分查找，则时间复杂度为： O（log2n）。

（7）理想情况下，在散列表中查找一个元素的时间复杂度为： O（1）。

（8）在关键字序列（7，10，12，18，28，36，45，92）中，用二分查找法查找关键字92，要比较 4 次才找到。

（9）设有100个元素，用二分查找时，最大的比较次数是 7 次。

（10）对二叉排序树进行查找的方法是用待查的值与根结点的键值进行比较，若比根结点小，则继续在左子树中查找。

（11）二叉排序树是一种动态查找表。

（12）哈希表是按散列存储方式构造的存储结构（13）哈希法既是一种存储方法，又是一种查找方法。

（14）散列表的查找效率主要取决于散列表造表时选取的散列函数和处理冲突的方法。

单元练习6一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳）（√）（1）n维的多维数组可以视为n-1维数组元素组成的线性结构。

（√）（2）稀疏矩阵中非零元素的个数远小于矩阵元素的总数。

（ㄨ）（3）上三角矩阵主对角线以上（不包括主对角线中的元素），均为常数C。

（√）（4）数组元素可以由若干个数据项组成。

（√）（5）数组的三元组表存储是对稀疏矩阵的压缩存储。

（ㄨ）（6）任何矩阵都可以进行压缩存储。

（ㄨ）（7）广义表是线性表的推广，所以广义表也是线性表。

（ㄨ）（8）广义表LS=（a0,a1,……an-1），则an-1是其表尾。

（√）（9）广义表((a,b),a,b)的表头和表尾是相等的。

（√）（10）一个广义表的表尾总是一个广义表。

二．填空题（1）多维数组的顺序存储方式有按行优先顺序存储和按列优先顺序存储两种。

（2）在多维数组中，数据元素的存放地址可以直接通过地址计算公式算出，所以多维数组是一种随机存取结构。

（3）在n维数组中的每一个元素最多可以有 n 个直接前驱。

（4）输出二维数组A[n][m]中所有元素值的时间复杂度为O(n*m) 。

（5）数组元素a[0..2][0..3]的实际地址上2000，元素长度是4，则LOC[1,2]= 2024 。

LOC[1,2]=2000+（1*4+2）*4（6）稀疏矩阵的三元组有 3 列。

（7）稀疏矩阵的三元组中第1列存储的是数组中非零元素所在的行数。

（8）n阶对称矩阵，如果只存储下三角元素，只需要 n（n-1）/2 个存储单元。

（9）稀疏矩阵A如下图所示，其非零元素存于三元组表中，三元组（4，1，5）按列优先。

稀疏矩阵AA=（10）稀疏疏矩阵的压缩存储方法通常有三元组表和十字链表两种。

（11）任何一个非空广义表的表尾必定是广义表（或子表）。

（12）tail(head((a,b),(c,d))= b 。

（13）设广义表((a,b,c))，则将c分离出来的运算是 head(tail(tail(head(L)))) 。

数据结构期末试题及答案. E 卷一、单项选择题1、线性表若采用链式结构时，要求内存中可用存储单元的地址( )。

A. 必须是连续的B. 部分地址必须是连续的C. 一定是不连续的D. 连续不连续都可以2、判定一个栈ST(最多元素为m0)为空的条件是( )。

A. ST-一、单项选择题1、线性表若采用链式结构时，要求内存中可用存储单元的地址( )。

A. 必须是连续的B. 部分地址必须是连续的C. 一定是不连续的D. 连续不连续都可以2、判定一个栈ST(最多元素为m0)为空的条件是( )。

A. ST：addr(15)=4 addr(38)=5 addr(61)=6 addr(84)=7 其余地址为空如用二次探测再散列处理冲突，关键字为49的结点的地址是( )。

A. 8B. 3C. 5D. 95、在线索化二叉树中，t所指结点没有左子树的充要条件是( )。

A. t-5、在线索化二叉树中，t所指结点没有左子树的充要条件是( )。

A. t：abdce; 广度优先遍历序列为：abedc26、27、答：（1）比较次数分别为3、2、1、1。

（2）平均查找长度ASL=(3+2+1+1+2)/5=1.828、初始：17，18，60，40，7，32，73，65，85 第1趟：17，18，40，7，32，60，65，73，85 第2趟：17，18，7，32，40，60，65，73，85 第3趟：17，7，18，32，40，60，65，73，85 第4趟：7，17，18，32，40，60，65，73，85 第5趟：7，17，18，32，40，60，65，73，85四、算法阅读题（每小题6 分，共12 分）29．(1)flag = 0；(2)1到n-1；(3)R[j＋1].key；(4)R[j] =R[j＋1]；(5)flag＝030．q = p-.rlink q-link ＜0 q =(－1)*(q-llink)q = q-.llink五、算法设计题（共8分）参考答案void swap(dnode*p) { dnode * q; q=p-right; if (q==NULL ) printf(“不能进行交换!/n”); else { p-right=q-right; p-right-left=p; p-left-right=q; q-left=p-left; p-left=q; q-right=p; } }word 资料达到当天最大量API KEY 超过次数限制。

2022年厦门理工学院数据科学与大数据技术专业《计算机系统结构》科目期末试卷B（有答案）一、选择题1、利用时间重叠概念实现并行处理的是( )。

A.流水处理机B.多处理机C.并行（阵列）处理机D.相联处理机2、计算机组成设计不考虑( )。

A.专用部件设置B.功能部件的集成度C.控制机构的组成D.缓冲技术3、“启动I/O”指令是主要的输入输出指令，是属于（）。

A.目态指令B.管态指令C.目态、管态都能用的指令D.编译程序只能用的指令4、从计算机系统结构上讲，机器语言程序员所看到的机器属性是（）A.计算机软件所要完成的功能B.计算机硬件的全部组成C.编程要用到的硬件组织D.计算机各部件的硬件实现。

5、开发并行的途径有（），资源重复和资源共享。

A.多计算机系统B.多道分时C.分布式处理系统D.时间重叠6、计算机系统的层次结构按照由高到低的顺序分别为（）。

A.高级语言机器级，汇编语言机器级，传统机器语言机器级，微程序机器级B.高级语言机器级，应用语言机器级，汇编语言机器级，微程序机器级C.应用语言机器级，传统机器语言机器级，汇编语言机器级，操作系统机器级D.应用语言机器级，操作系统机器级，微程序机器级，传统机器语言机器级7、在操作系统机器级，一般用（）程序（）作业控制语句。

A.汇编程序，翻译B.汇编程序，解释C.机器语言，解释D.机器语言，翻译8、1TFLOPS计算机能力，1TBYTE/S的I/O带宽和（）称为计算机系统的3T性能目标。

A，1TBYTE 硬盘容量B.1TBYTE 软盘容量C.1TBYTE 主存容量D.A和B9、对机器语言程序员透明的是( )。

A.中断字B.主存地址寄存器C.通用寄存器D.条件码10、浮点数尾数基值rm=8，尾数数值部分长6位，可表示的规格化最小正尾数为( )A.0.5B.0.25C.0.125D.1/64二、填空题11、评价地址码个数不同的4种指令的优缺点的主要标准是________和________12、输入输出设备的异步性、实时性、与________三个特点是现代计算机系统必须具备的共同特性。

一、选择题。

(每小题2分，共40分)(1) 计算机识别.存储和加工处理的对象被统称为____A____。

A.数据B.数据元素C.数据结构D.数据类型(2) 数据结构通常是研究数据的____ A _____及它们之间的联系。

A.存储和逻辑结构B.存储和抽象C.理想和抽象D.理想与逻辑(3) 不是数据的逻辑结构是____ A ______。

A.散列结构B.线性结构C.树结构D.图结构(4) 数据结构被形式地定义为<D,R>,其中D是____ B _____的有限集，R是____ C _____的有限集。

A.算法B.数据元素C.数据操作D.逻辑结构(5) 组成数据的基本单位是____ A ______。

A.数据项B.数据类型C.数据元素D.数据变量(6) 设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构A是____ A ______。

A.线性结构B.树型结构C.图型结构D.集合(7) 数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为___ C ____。

A.存储结构B.逻辑结构C.顺序存储结构D.链式存储结构(8) 在数据结构的讨论中把数据结构从逻辑上分为___ A ____。

A.内部结构与外部结构B.静态结构与动态结构C.线性结构与非线性结构D.紧凑结构与非紧凑结构(9) 对一个算法的评价，不包括如下____ B _____方面的内容。

A.健壮性和可读性B.并行性C.正确性D.时空复杂度(10) 算法分析的两个方面是__ A ____。

A.空间复杂性和时间复杂性B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性(11) 线性表是具有n个___ C _____的有限序列（n≠0)。

A.表元素B.字符C.数据元素D.数据项(12) 线性表的存储结构是一种____ B ____的存储结构。

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。