数据结构中期考试试卷.doc

数据结构期中考试试卷(供2012级计算机专业用)一、单项选择题，在括号内填写所选择的标号（每小题1分，共20分）1、算法指的是（ ） A计算机程序 B解决问题的计算方法 C排序算法 D解决问题的有限运算序列2、如下陈述中正确的是（ ） A串是一种元素仅为字符的线性表B串的长度必须大于零 C串中元素只能是字母 D空串就是空白串3、 在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（ ）。A. O(1)B. O(n2) C. O(n)D. O(n/2)4、 当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（ ）。A. n-2 B. n-1C. n D. n+15用链表表示线性表的优点是 （ ）。(A)便于随机存取(B)花费的存储空间较顺序存储少(C)便于插入和删除(D)数据元素的物理顺序与逻辑顺序相同6在少用一个元素空间的循环队列QU ( m0为最大队列长度(以元素为单位)，front和rear分别为队列的队头指针和队尾指针 ) 中，当队列非空时，若插入一个新的数据元素，则其队尾指针rear的变化是( )。AQU-rear=(QU-front+1) % m0 BQU-rear=(QU-rear+1) % m0CQU-rear=(QU-front+1) DQU-rear=(QU-rear+1) 7 设有S1=“ABCDEFG”，S2=“PQRST”，函数con(x，y)返回x和y串的连接串，subs(s,i，j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(S1，2，len(S2)，subs(S1，len(S2)，2)的结果是( )。ABCDEF B. BCDEFG C. BCPQRST D. BCDEFEF8、在一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较（ ）个元素结点。 (A)n2 (B)n (C)(n+1)2 (D)(n-1)29串的长度是( )。 (A)串中不同字符的个数 (B)串中不同字母的个数 (C)串中所含字符的个数n(nO) (D)串中所含字符的个数n(n0)10.表达式a*(b-c)+d的后缀表达式是（ ）。 Aabcd*-+ B. abc-*d+ C. abc*-d+ D. +-*abcd 11. 假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为( )。 A. front = rearB. front != NULL C. rear != NULL D. front = NULL12、带头结点的单链表first为空的判定条件是（ ）。A. first = NULL; B. first-link = NULL;C. first-link = first; D. first != NULL;13. 设有一个nn的对称矩阵A，将其下三角部分按行存放在一个一维数组B中，A00存放于B0中，那么第i行的对角元素Aii存放于B中（ ）处。 A. (i+3)*i/2 B. (i+1)*i/2 C. (2n-i+1)*i/2 D. (2n-i-1)*i/214. 已知单链表A长度为m，单链表B长度为n，若将B联接在A的末尾，其时间复杂度应为（ ）。 A. O(1) B. O(m) C. O(n) D. O(m+n) 15. 设有一个递归算法如下 int fact(int n) /n大于等于0 if(nnext=p-next; p-next=s; ）3. 在链表中进行插入和( )操作的效率比在顺序存储结构中进行相同操作的效率高。4需要压缩存储的矩阵可分为特殊矩阵和（ ）矩阵两种。5栈的插入和删除只能在栈的顶端进行，后进栈的元素必定先被出栈，所以又把栈称作( )表；队列的插入和删除运算分别在两端进行，进行插入的一端叫做( )，进行删除的一端叫做( )，先进队的元素必定先出队，所以又把队列称作( )表。6. 某广义表A =( a ,( b , c , d ) ，e) ，则GetLength(A)=( ), GetHead(A)=( ),GetTail(A)=( )。7. 若有广义表表示为A=（a，(b，(c, d，(e, f)），则A的深度为（ ）。8. 链表适用于( )查找。9.设有一个顺序栈S，元素S1，S2，S3，S4，S5，S6依次进栈，如果6个元素的出栈顺序为S2，S3，S4，S6，S5，S1，则顺序栈的容量至少应为( )。10在一个长度为n的向量中的第i个元素(1in)之前插入一个元素时，需向后移动（ ）个元素。三、判断题，在每小题后面的括号内打表示正确或打表示错误（每小题1分，共10分）1线性表的逻辑顺序与存储顺序总是一致的。( )2. 顺序表和一维数组一样，都可以按下标随机（或直接）访问。( )3. 用非递归方法实现递归算法时一般要使用递归工作栈。( )4在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。（ ）5.栈和队列都是限制存取点的线性结构（ ）6设有两个串p和q，其中q是p的子串，把q在p中首次出现的位置作为子串q在p中的位置的算法称为匹配。 ( )7数据元素是数据的基本单位。 ( )8在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。（ ）9在单链表中任何两个元素的存储位置之间都有固定的联系，因为可以从头结点进行查找任何一个元素( )。10数组是一种复杂的数据结构，数组元素之间的关系，既不是线性的，也不是树形的 ( )四、简答题（每小题5分，共20分） 1. 设有一个二维数组Amn，按行优先存放于一个连续的存储空间中，A00的存储地址是200，每个数组元素占2个存储单位，则： 写出二维数组（m*n）按行为主序存储后LOC(aij)地址计算公式是： 当m=10,n=20时，数组元素A810的存储地址是多少？2有下列程序段i=s=0While(sdatedate) return(1)； if (s1dates2date) return(1)；s1=s1-next; _ _； if (_ _) return(-1)； if (s1!=NULL & s2=NULL) return(1)； _ _ _； 5、给定如下二叉树，请分别写出对该二叉树进行前序、中序和后序遍历的结果。6假设用于通信的电文仅由6个字母组成(设为A B C D E F )，字母在电文中出现的频率分别为：7，19，2，6，32，3。试为这6个字母设计哈夫曼编码并画出哈夫曼树(构造哈夫曼树时按子树根结点值左小右大的规则进行)。7. 已知用有序链表存储整数集合的元素，其中a和b分别为指向存储集合2，4，5，7，9，12和2，4，5，7，9的链表的头指针；阅读算法f44，并回答下列问题：写出执行f44（a,b）的返回值；简述算法f41的功能；写出算法f41的时间复杂度。算法如下：int f44(LinkList ha,LinkList hb) /LinkList是带有头结点的单链表 /ha和hb分别为指向存储两个有序整数集合的链表的头指针 LinkList pa,pb; pa=ha-next; pb=hb-next; while(pa & pb & pa-data=pb-data) pa=pa-next; pb=pb-next; if(pa=NULL & pb=NULL) return 1; else return 0; ：8对于下图,请写出对应的邻接矩阵,给出v1,v2二个顶点的度,该图是否为强连通图并说明理由？85615V1V4V3V212算法设计1. 有一个单链表（不同结点的数据域值可能相同），其头指针为head，编写一个函数计算数据域为x的结点个数。2. 二叉排序树的结点类型定义为：typedef struct node /*二叉排序树结点定义*/ int data; /*结点值*/ struct node *lchild, *rchild; /*左、右孩子指针*/ BitNODE;试编写一个在二叉排序树中查找结点值为x算法。BitNODE *search(NODE *t, int x) /*二叉排序树的非递归查找*/3. 试编写一个函数，在一个具有链接存储结构的表中删除其值为x的所有结点。 说明：设head 指向链表头结点，结点结构含二个域（一个整形数据域data，一个指向下一结点的链接域next），建立函数void del_link(NODE *head,int x)实现题目所要求的操作。4. 有一个有序单链表（从小到大排序），表头指针为head，编写一个函数向该单链表中插入一个元素为x的结点，使插入后该链表仍然有序。 说明：设head