发布时间 : 星期二 文章算法与数据结构其中测试试卷-ans更新完毕开始阅读9311da47be1e650e52ea991e
福州大学至诚学院期中试卷 （A）卷
2011——2012 学年第2学期 课程名称《算法与数据结构》考试日期：2012年4月12日 主考教师：陈亦萍 考试时间：120分钟 专业： 班级： 考生学号： 考生姓名： 注意：试卷评阅统一使用红色笔，要求对的打“√”，错的打“×”，并采用扣分的方法评定。 题号 一 题分 得分
二 三 四 五 六 七 八 九 总分 100 累分人签名 考生注意事项：1、本试卷共 6 页，请查看试卷中是否有缺页。
2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。
一、选择题（每小题 2 分，共40分）
得分
1、以下数据结构中，哪一个是非线性结构？（ A ）
A．树 B. 字符串 C. 队列 D. 栈
2、在存储数据时，通常不仅要存储各数据元素的值，而且还要存储（ C ） A．数据的操作方法 B. 数据元素的类型
C. 数据元素之间的关系 D. 数据的存取方法 3、算法的时间复杂度取决于（ D ）
A．问题的规模 B. 待处理数据的初态 C. 执行的次数 D. A和B 4、在下面的程序段中，对x的赋值语句的频度为（ C ）
FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1;
A．O(2n) B．O(n) C．O(n) D．O(log2) 5、在线性表中，除了开始元素外，每个元素（ A ）
A. 只有唯一的前驱元素 B. 只有唯一的后继元素 C．有多个前驱元素 D. 有多个后继元素
第1页 共6页
2
n
评卷人
6、下面关于线性表的叙述中，错误的是哪一个？（ B ）
A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。
7、在n个结点的线性表的数组表示中，以下算法的时间复杂度O(1)的操作是（ C ） Ⅰ. 访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） Ⅱ. 在最后一个结点后插入一个新的结点 Ⅲ. 删除第一个结点
Ⅳ. 在第i个结点后插入一个结点（1≤i≤n）
A．Ⅰ B. Ⅱ,Ⅲ C. Ⅰ, Ⅱ D. Ⅰ, Ⅱ, Ⅲ
8、在一个长度为n的带头结点的单链表h上，设有尾指针r,则执行（ B ）操作与链表的表长有关。
A．删除单链表中的第一个元素
B．删除单链表中的最后一个元素(需要将最后一个结点的前驱结点的next=NULL) C．在单链表第一个元素前插入一个新元素 D．在单链表最后一个元素后插入一个新元素
9、将长度为n的单链表连接在长度为m的单链表后面，其算法的时间复杂度采用大O形式表示应该是（ C ） A．O(1) B．O(n) Ｃ．O(m)//指针定位到m链表的最后一个元素 Ｄ．O(n+m) 10、设单链表中结点的结构为（data, link）。已知指针p所指结点不是尾结点，若在*p之后插入结点*s，则应执行的操作是（ D ）。
A. s->link=p; p->link=s; B. p->link=s; s->link=p; C. s->link=p->link; p=s; D. s->link=p->link; p->link=s;
11、设单循环链表中结点的结构为（data, link），且rear是指向非空的带表头结点的单循环链表的尾结点的指针。若想删除链表第一个结点，则应执行的操作是（ D ）。 A. s = rear; rear = rear->link; delete s; B. rear = rear->link; delete rear; C. rear = rear->link->link; delete rear;
D. s = rear->link->link; rear->link->link = s->link; delete s; 12、带表头的双向循环链表的空表满足（ B ）。
A．first＝NULL; B. first->rLink==first
C．first->lLink==NULL D．first->rLink==NULL 13、栈和队列的共同点是（ C ）。
A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点
第2页 共6页
14、设有一个空栈，栈顶指针为1000H,每个元素需要1个存储单元，在执行Push、Push、Pop、Push、Pop、Push、Pop、Push操作后，栈顶指针的值为（ A ）
A．1002 H B. 1003 H C. 1004 H D. 1005 H 15、用链接方式存储的队列，在进行删除运算时（ A ）。
A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改16、假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear，则判断队空的条件为（ D ）
A．front+1 == rear Ｂ．rear+1 == front C.．front == 0 D． front == rear 17、为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓存区，主机将要输出的数 据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（ B ） A．栈 B．队列 Ｃ. 树 D. 图
18、在系统实现递归调用时需利用递归工作记录保存（ C ），当递归调用程序执行结束时通过它将控制转到上层调用程序。
A．调用地址 B．递归入口 C．返回地址 D．递归出口 19、多维数组实际上是由嵌套的（ A ）实现的。
A. 一维数组 B. 多项式 C. 三元组表 D. 简单变量 20、对特殊矩阵采用压缩存储的主要目的是（ D ）
A．表达变得简单 B．对矩阵元素的存取变得简单
C．去掉矩阵中多余的元素 D．减少不必要的存储空间
二、填空题（每空格 2 分，共20分）
得分
1、 数据结构包括逻辑结构、____存储结构_______和数据的运算三个方面。 2、 串abaabbabab的next数组值为___0112231234________。
3、 若设一个n*n的矩阵A的开始存储地址LOC(0, 0) 及元素所占存储单元数d已知，按行存储时其任意
一个矩阵元素a[i][j]的存储地址为___ LOC(0, 0)+(i*n+j)*d __
4、 当一个作为实际传递的对象占用的存储空间较大并可能被修改时，应最好说明为___引用类型____(数
据类型)，以节省参数值的传输时间和存储参数的空间。
5、 用S表示进栈操作，用X表示出栈操作，若元素的进栈顺序是1234，为了得到1342的出栈顺序，相
应的S和X的操作序列为___SXSSXSXX_________
6、对于顺序表，访问第i个位置的元素和在第i个位置插入一个元素的时间复杂度分别为___O(1)____和
____O(n)____
第3页 共6页
评卷人
7、给定有n个元素的一维数组，建立一个有序单链表的最少时间复杂度为____O(nlogn)__
8、在程序运行过程中不能扩充的数组是____静态___分配的数组。这种数组在声明它时必须指定它的大小。 9、顺序存储的循环队列的QueueMaxSize=n,则该队列最多可存储___n-1__个元素.
三、判断题（每小题 1分，共10分）
得分 1、（ × ）算法和程序原则上没有区别，在讨论数据结构时二者是通用的。
2、（ × ）线性表中的数据元素可以是各种各样的，同一线性表中的元素可以属于不同的数据对象，相邻数据元素之间存在着序偶关系。
3、（ × ）数组是一种静态的存储空间分配，就是说，在程序设计时必须预先定义数组的数据类型和存储空间大小，由编译程序在编译时进行分配。
4、（ √ ）链式栈与顺序栈相比, 一个明显的优点是通常不会出现栈满的情况。
5、（ √ ）递归调用算法与相同功能的非递归算法相比，主要问题在于重复计算太多，而且调用本身需要分配额外的空间和传递数据和控制，所以时间与空间开销通常都比较大。 6、（ √ ）KMP算法的特点是在模式匹配时指示主串的指针不会变小。 7、（ √ ）一个广义表的表尾总是一个表。
8、（ ）在顺序表中，逻辑上相邻的元素在物理位置上不一定相邻。
9、（ ）将f = 1 + 1/2 + 1/3+ … + 1/n转化为递归函数时，递归部分为f (n) = f (n-1) + 1/n，递归结束条件为f (1) = 1。
10、（ × ）对任何数据结构，链式存储结构一定优于顺序存储结构。
评卷人 四、综合应用题（每小题 10分，共30分）
得分 1、假设采用以下两种结点的链表作为广义表的存贮结构，表结点：(tag=1,hp,tp), 原子结点；(tag=0,data)。已知广义表LS=( ( ) , (e) , (a , (b , c , d ) ) )。 （1）画出广义表LS的头尾链表法存储结构图。（4分） （2）写出表的长度与深度。（2分）
（3）用取表头head(LS)和取表尾tail(LS)的基本运算，求出b。（4分）
第4页 共6页
评卷人