数据结构(A卷)试题

湖南人文科技学院邕控系 通信工鶴业2007级名姓评卷人一、填空题：（每空1分，共20分）2009-2010学年第一学期数据结构课程考核试卷A）考核方式：（闭卷）考试时量：120分钟题号-二三四总分合分人复査人1、数据结构被形式地定义为（D, R）,其中D是的有限集合，R是D上的有限集合。2、一个算法的效率可分为效率和效率。3、在n个结点的单链表中，查找某个数据的时间复杂度为。n个结点的顺序表存储时，查找某个数据的时间复杂度为。4、在一个循环队列中，队首指针指向队首元素的位置。号学 师教课任5、在具有n个单元的循环队列中，队列满时共有个元素。6、设串 t二“I am a student good,串 Sub=Substring（t, 8, 7）,那么 Sub=。7、假设有二维数组,每个元素用相邻的6个字节存储，存储器按字节编址。已知A的存储位置为1000,按行优先存储，贝lj A的地址为；若按列优先存储时，则A的地址为。8、设一棵完全二叉树中有21个结点，如果按照从上到下、从左到右的顺序从1开始顺序编号，则编号为8的双亲结点的编号是,编号为8的左孩子结点的矩旦曰硼万疋O9、在解决计算机主机与打印机之间速度不匹配时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机从该缓冲区中取出数据打印。该缓冲 区应该是一个结构，其主要特点是。10、算法是指令的有限序列，其中每一条指令表示一个或多个操作，此外，一个算法还具有五个重要特性，它们分别是、有零或多个输入和有一或多个输出。11、在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的、和三项。-评卷人二、选择题：（每空2分，共30分）1. （）是具有相同特性数据元素的集合，是数据的子集。A.数据符号B.数据对象C.数据D.数据结构2. 用链表表不线性表的优点是（）oA.便于随机存取B.花费的存储空间比顺序表少C.便于插入与删除D.数据元素的物理顺序与逻辑顺序相同3. 堆栈的输入序列为（A,B,C,D）,不可能的输出有（）。A. （A, B, C, D）B. （D, C, B, A）C. （A, C, D, B）D . （C, A, B, D）4. 在数组表示的循环队列中，front、rear分别为队列的头、尾指针，maxSize为数组 的最大长度，队满的条件是（）。A. front二maxSizeB. （rear+1）%maxSize=frontC. rear=maxSizeD. rear=front5. 设有一个对称矩阵A,采用压缩存储方式，以行序为主序存储all为第一个元素，其存储地址为1,每个元素占一个地址空间，则 於5地址为（）。A. 23B. 33C. 18D. 406. 若已知一棵二叉树先序序列为ABCDEFG,中序序列为CBDAEGF,则其后序序列为（）。A. CDBGFEAB. CDBFGEAC. CDBAGFED. BCDAGFE7. 采用折半查找方法进行查找，数据文件应为（），且限于（）。A.有序表 顺序存储结构B有序表 链式存储结构C.随机表 顺序存储结构D.随机表 链式存储结构8. 执行下面程序段时，执行S语句的次数为（）for（int I二1;I二n;I+）for（int j二1;j二I;j+）S;A. ri2B. n2/2C. n （n+1）D. n （n+1） /29. 串是一种特殊的线性表，其特殊性体现在（）A.可以顺序存储B.数据元素是一个字符C.可以链接存储D.数据元素可以是多个字符10. 由五个分别带权值为9, 2, 3, 5, 14的叶子结点构成的一棵哈夫曼树，该树的带权 路径长度为（）。A. 60B. 66C. 67D. 5011深度为 5 的二叉树至多有（ ）个结点。A10B16C31D3212. 数组的逻辑结构不同于下列（ ）的逻辑结构。A.线性表B.栈C. 队列D. 树13.设指针变量p指向单链表结点A,则删除结点A的后继结点B需要的操作为（）。A. p-next=p-next-nextB. p=p-nextC. p=p-next-nextD. p-next=p14.将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（）。A. 100B. 40C. 55D. 8015.设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为A. 3B. 4C. 5D. 1）。得分评卷人12三、判断题（每题1 分，共10分）345678.三个结点的二叉树和三个结点的树一样，都具有三种不同的形态。 算法可以没有输入，但是必须有输出 。对链表进行插入和删除操作时不必移动链表中结点。 子串“ABC”在主串“AABCABCD”中的位置为2。入栈操作和入队列操作在链式存储结构上实现时需要考虑栈溢出的情况。 顺序表查找指的是在顺序存储结构上进行查找。列是插入与删除操作分别在表的两端进行的线性表，是一种先进后出结构 线性表在顺序存储时，逻辑上相邻的元素必在存储的物理位置次序上相邻）链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动将后续各个单元向前移动。（ ）10. 二叉树中的叶子结点就是二叉树中没有左右子树的结点。（ ）9得分评卷人四、程序题（1、2题每题 5分, 3、4题每题 6分, 5、6 题每题 9 分,共 40 分）1.写出程序段的功能,如果输入数据为 254，写出输出结果。 （5分）void conversion()Stack s;int n;SElemType e; initstack(s); printf(Please input number:); scanf( “ %d ” ,&n);while(n) push(s,n%9);n=n/9; while(!stackempty(s) pop(s,e);printf(“%d”,e); 该程序的功能为：输入 254，输出数据为：2、读函数，指出函数的功能。 (5分)LinkList mynote(LinkList L)/L 是不带头结点的单链表的头指针if(L&L-next) q=L；L=Lnext；p=L；S1： while(pnext)p=pnext；S2： pnext=q；qnext=NULL； 共 7 页第 4 页if(s1is2j)return 1;else if(s1is2j)return -1; else i+,j+;if(s1i)return 1;else if(s2j) return -1;else return 0; 函数 f 的功能是：返回值-1 的含义：返回值0的含义：返回值1的含义： 请回答下列问题： 1)说明语句 S1 的功能(2)说明语句组 S2 的功能；(3)设链表表示的线性表为(a.a，,an)，写出算法执行后的返回值所表示的线性 表。3. 请在标号处填写合适的语句。完成下列程序。(每空2 分，共6 分)int Binary_Search(SStable ST，KeyType key) /*在关键字升序排列的表T中查找关键字为key的数据元素，若找到返回该元素在表中 的位置，否则，返回0 */intmid， low， high；low=1；high=length； while(low=high)/* 非空，进行比较测试 */mid二；if(keyST.elemmid.key) ；else return mid；return 0；4. 指出下面函数f的功能及返回值的含义。(6分)int f(char s1,char s2)int i=0,j=0;5. 设计判断单链表中元素是否是递增的算法。(9分)结点定义如下：typedef struct Lnodeint date; struct Lnode *next;LNode, *Link；函数定义如下：BOOL InSort (Link head)head为链表的头结点，头结点中存有数据。若是升序排列，返回true；否则返回false；如果head = = NULL或者链表只有一个结点，返回true。写出该函数的函数体。BOOL InSort (Link head)共 7 页第 5 页6. 写出链栈中数据出栈的函数。(9分)堆栈中的结点定义如下：tyedef struct Stackchar date;struct Stack *next; *LinkStack;head为栈顶指针。出栈函数定义如下：void Pop (LinkStack head)；Void Pop (LinkStack head)共7页第7页