数据结构期中测试题.doc

数据结构期中测试题 注意：满分100分，第四题为选做题，计分不在总分之内 一、选择题（共53题，每题1分，共53分） 1.下列叙述中关于好的编程风格，正确的描述是（ ） A.程序中的注释是可有可无的 B.对递归定义的数据结构不要使用递归过程 C.递归应是封闭的，尽量少使用全局变量 D.多采用一些技巧以提高程序运行效率 2.通常从正确性、易读性、健壮性、高效性等四个方面评价算法(包括程序)的质量。以下解释错误的是（ ） A.正确性 算法应能正确地实现预定的功能(即处理要求) B.易读性 算法应易于阅读和理解 以便于调试 修改和扩充 C.健壮性 当环境发生变化时，算法能适当地做出反应或进行处理，不会产生不需要的运行结果 D.高效性 即达到所需要的时间性能 3.以下说法正确的是（ ） A.数据元素是数据的最小单位 B.数据项是数据的基本单位 C.数据结构是带有结构的各数据项的集合 D.数据结构是带有结构的数据元素的集合 4.下面程序段的时间复杂度是（ ） for (i=0; i＜n; i++) for (j=1; j＜m; j++) A[i][j]=0; A.O (n) B.O(m+n-1) C.O(m+n) D.O(m*n) 5.下面关于线性表的叙述中，错误的是（ ） A.线性表采用顺序存储，必须占用一片连续的存储单元。 B.线性表采用顺序存储，便于进行插入和删除操作。 C.线性表采用链接存储，不必占用一片连续的存储单元。 D.线性表采用链接存储，便于插入和删除操作。 6.链表不具有的特点是： A.可随机访问任一个元素 B.插入删除不需要移动元素 C.不必事先估计存储空间 D.所需空间与线性表长度成正比 7.线性表是具有n个（ ）的有限序列 A.表元素 B.字符 C.数据元素 D.数据项 8.设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用（ ）最节省时间。 A.单链表 B.单循环链表 C.带尾指针的单循环链表 D.带头结点的双循环链表 9.若某线性表中最常用的操作是取第个元素和找第个元素的前趋元素，则采用存储方式最节省时间。 .顺序表 单链表 双链表 单循环链表 10.11.在长度为n的顺序表的第i（1≤i≤n+1）个位置上插入一个元素，元素的移动次数为（ ） A.n-i+1 B.n-i C.i D.i-1 12.线性表（ a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（ ）A.O（i） B.O（1） C.O（n） D.O（i-1） 13.在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（ ） A.p-link=s;s-link=p-link; B.s-link=p-link;p-link=s; C.p-link=s;p-link=s-link; D.p-link=s-link;p-link=s; 14.在一个单链表中，若删除p所指结点的后续结点，则执行（ ） A.p-link=p-link-link; B.p=p-link; p-link=p-link-link; C.p-link=p-link; D.p=p-link-link; 15.线性表若采用链表存储结构时，要求内存中可用存储单元的地址 A.必需是联系的 B.部分地址必须是连续的 C.一定是不连续的 D.连续不连续都可以 16link-＞link=head，则（ ） A.p指向头结点 B.p指向尾结点 C.*p的直接后继是头结点 D.*p的直接后继是尾结点 17.完成在双循环链表结点p之后插入s的操作是（ ） A． p-rlink=s ; s-llink=p; p-rlink-llink=s ; s-rlink=p-rlink; B． p-rlink-llink=s; p-rlink=s; s-llink=p; s-rlink=p-rlink; C． s-llink=p; s-rlink=p-rlink; p-rlink=s; p-rlink-llink=s ; D． s-llink=p; s-rlink=p-rlink; p-rlink-llink=s ; p-rlink=s; 18.栈和队列的共同点是（ ） A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D