数据结构期末考卷12-13级

《数据结构期末考卷12-13级》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、诚信应考考出水平考出风格浙江大学城市学院2012—2013〈〈学年第一学期期末考试试卷数据结构基础开课单位：计箅分院；考试形式：闭卷；考试时间：2013年1月12日:所需时间：120分钟题序—•」二四五/、总分得分评卷人:得分一.选择题(本大题共15题，每题1分，共15分)參攀<1.数据结构形式地定义为(K，R),其屮《是的有限集合，R是K上的关系的有限集合。A.算法B.数据元素C.数据操作D.逻辑结构2.数据在计算机内存中的表示足指。A.数据的存储结构B.数据结构C.数裾的逻辑结构D.数裾元素之间的关系3.某算法

2、的吋间复杂度为f(n)=8log2n+5n+2,若采川数景级的形式表示，应该是。A.O(8log2n+5n+2)巳.O(log2n+n)C.O(n)D.O(log2n)4.与单链表相比，双链表的优点之一是oA.插入、删除操作更加简单B.可随机访MC.可以省略表失指针或表尾指针D.顺序访问相邻结点更加灵活5.设线性表L=(a1，a2,……an),下列关于线性表的叙述正确的是。A.每个元素都有一个直接前驱和一个直接后继B.线性表中至少有一个元素C.表中元素排列顺序必须按lb小到大或凼大到小D.除第一个和最后一个元素外，

3、其余每个元素都奋且只奋一个直接前驱和一个直接后继第1页共7页1.以下关于顺序存储结构的叙述中，是不正确的。A.空间利用率高B.逻辑上相邻的结点物理上不必邻接C.可以通过计算机直接确定笫i个结点的存储地址D.插入、删除运算操作不方便2.以下不足栈的基本运算的足。A.删除栈顶元素B.删除桟底元素C.判断栈是否为空D.将栈置为空栈3.14一个栈指针为HS的链式栈中插入一个s所指的结点吋，则执行oA.HS->NEXT=S;B.S->NEXT=HS->NEXT;HS->NEXT=S;C.S->NEXT=HS;HS=S;D.S

4、->NEXT=HS;HS=HS->NEXT;4.在一个非空的链式队列中，假没f和r分别为队头和队尾指针，则插入s所指的结点运算是。A.f->next=s;f=s;巳.r->next=s;r=s;C.s->next=s;r=s;D.s->next=f;f=s;5.数组Q[0..n-1]川来表示一个环形队列，f为当前队头元素的前一位置，r为队M元素的位置,假定队列屮元素个数的总数小于n,计算队列中元素个数的公式为oA.r-fB.n+f-rC.n+r-fD.(n+r-f)modn6.递归函数调用时，为保存局部变量及返回地

5、址，要用一•种称为的数据结构。A.队列B.桟C.多维数组D.线性表7.将一棵有1000个结点的完全二叉树从上到下，从左到右依次进行编号，根结点的编号为1,则编号为49的结点的右孩子编号为。A.98B.99C.50D.没有右孩了8.对二义树的结点从1开始进行编号，要求每个结点的编号人于其左右孩子的编号，同一结点的左右孩子屮，左孩子的编号小于其右孩子的编号，可采用遍历实现编号。A.先序B.中序C.后序D.层序9.假设-•个有n个顶点和e条边的有向图用邻接表表示，则删除与菜个顶点相关联的所有边的吋间复杂度是。A.O(n)

6、B.0(e)C.O(n+e)D.O(n*e)10.分析下ifd的无句图，从顶点A出发的深度优先搜索序列可以为。B.ABCDEFGHD.ACEHFDBGA.ABDGEHFCC.ABDEGCFH得分二.填空题（本大题共20个空，每个空1分，共20分）1.线性结构屮元素之问存在着（1）关系,图形结构屮元素之间存在着（2）关系。2.数据的逻辑结构毡括⑶和⑷两大类。3.兑法评价的五个方面是：正确性、稳健性、可读性、⑸和⑹。4.下而程序段的时间复杂度为⑺。for（i=0;i

7、[j]=0;5.对干一个长度为n的顺序存储的线性表，在表1插入元素的吋间S杂度为⑻，在表足插入元素的吋间复杂度为⑼。6.对于双向链表，删除一个结点需修改的指针域共有个。7.若对线性表进行的操作主要不足插入和删除，M该线性表宜采用（11）存储结构:若需频繁地对线性表进行插入和删除操作，则该线件表宜采用（⑵存储结构。8.栈和队列是-•种特殊的线性表，根据栈和队列的特征，栈是-•种⑽的线性表,队列是一种⑽的线性表。9.一个栈的输入序列是12345,则43512是否可能是找的输出序列？（回答是或否）03o10.对一棵M有n

8、个结点的二叉树，当它为-•棵（⑹二叉树吋.H有最小髙度:当它为一棵（⑺二义树时,具有最人高度。11.迕一个无肉阁中，所有顶点的度数之和等子所有边数（⑻倍,在一个有向阁中，所有顶点的入度之和等于所有顶点出度之和的（19）倍。12.图的广度优先搜索遍历算法需借助于哪一种数据结构？⑽。得分三.解答题（本大题共3题，每题6分，共18分）1.设有一个单循环链表p如下图