《13级《数据结构》期中试卷(打印)》由会员分享，可在线阅读，更多相关《13级《数据结构》期中试卷(打印)（2页珍藏版）》请在金锄头文库上搜索。
1、湖北理工学院 20142015 学年度第（1）学期试卷2013 级计算机学院本科各专业数据结构与算法期中试卷（）第 1 页 共 2 页* *班 级：*学 号：* 姓 名：*得分一、选择题（每小题 2 分，共 30 分）1下面程序段的时间复杂度是（ ） 。for(i=0;inext=NULL； Chead next=head； D. head!=NULL.7. 在头指针为 head 且表长大于 1 的单循环链表中，指针 p 指向表中某个结点，若 p-next-next=head，则（ ） 。Ap 指向头结点； B. p 指向尾结点； C*p 的直接后继是头结点； D. *p 的直接后继是尾结点.
2、8. 执行如下语句后，*(xp+2) 的值为int x =2,5,6,8,*xp; xp=x;A2 ； B. 5 ； C6 ； D. 8.9. 删除双链表中间某个结点，需要修改（ ）个指针域。A1 ； B. 2 ； C3 ； D. 4.10. 队列和栈的特征分别是（ ） 。A先进先出，先进后出； B. 先进先出，先进先出；C先进后出，先进先出； D. 先进后出，先进后出.11. 有 6 个元素按 6,5,4,3,2,1 的顺序进栈，问下列哪一个不是合法的出栈序列( )。A5,4,3,6,1,2； B. 4,5,3,1,2,6； C3,4,6,5,2,1； D. 2,3,4,1,5,6.12.
3、若用一个大小为 6 的数组来实现循环队列，且当前 rear 和 front 的值分别为 0 和 3，当从队列中删除一个元素，再加入两个元素后，rear 和 front 的值分别为（ ） 。A1 和 5； B. 2 和 4； C4 和 2； D. 5 和 1.13. 在计算机内实现递归算法时所需的辅助数据结构是（ ） 。A栈； B. 队列； C树； D. 图.14. 设树 T 的度为 4，其中度为 1,2,3 和 4 的结点个数分别为 4,2,1 和 1，则 T 中的叶子数为（ ） 。A5 ； B. 6 ； C7 ； D. 8.15. 具有 3 个结点的二叉树的所有不同形态的个数是（ ） 。A2
4、 ； B. 3 ； C4 ； D. 5.得分二、填空题（每小题 2 分，共 20 分）1. 著名计算机科学家沃思曾指出：算法+ =程序。2. 数据元素及其关系在计算机存储器内的表示，称为数据的 。3设顺序表第 1 个元素的存储地址是 2000，每个元素占 4 个字节，则第 41 个元素的存储地址是 。 4线性表中的每个结点最多有_前驱和_后继。5在有 n 个结点的单链表中，要删除指针 p 所指结点，需要找到它的 。 6栈是限制仅在表一端进行插入和删除运算的线性表，通常将这一端称为 。7为了充分利用向量空间，将队列的向量空间想象成一个首尾相连的圆环，这种方法克服了顺序队列的 现象。8循环队列用数
5、组 A0,m-1存放其元素值，已知其头尾指针分别是 front 和 rear，则当前队列的元素个数是 。9任意一棵二叉树中，若叶子结点个数为 m,度为 2 的结点个数为 n,在 m 和 n 之间的数学关系表达式为 。10具有 256 个结点的完全二叉树的深度是 。得分三、判断题（每小题 1 分，共 10 分）1. 算法一定要有输入和输出。 （ ）2. 顺序表结构适合进行顺序存取，而链表适合进行随机存取。 （ ）3. 线性表在物理存储空间中也一定是连续的。 （ ）4. 顺序存储结构只能用于存储线性结构。 （ ）5. 线性表的逻辑顺序与物理顺序总是一致的。( )6. 栈和队列逻辑上都是线性表。 （
6、 ）7. 单链表从任何一个结点出发，都能访问到所有结点。 （ ）8. 链表的每个结点中都恰好包含一个指针。 （ ）9. 符号 p-next 出现在表达式中表示 p 所指的那个结点的内容。 （ ）10. 满二叉树也是完全二叉树。 （ ）考试方式 闭 卷 考试时间：90 分钟题 号 一 二 三 四 五得 分总分* *班 级：*学 号：* 姓 名：*湖北理工学院 20142015 学年度第（1）学期试卷2013 级计算机学院本科各专业数据结构与算法期中试卷（）第 2 页 共 2 页* *班 级：*学 号：* 姓 名：*得分四、算法阅读题（每小题 5 分，共 15 分）1.阅读下列算法，并回答问题：（
7、1）假设顺序表 L=(3,7,11,14,20,51),写出执行 fun(&L,15)之后的 L。（2）假设顺序表 L=(4,7,10,14,20,51),写出执行 fun(&L,10)之后的 L。（3）简述算法的功能。void fun(SeqList *L,DataType x) int i=0,j;while(isize&xL-datai) i+;if(isize&x= L-datai) for(j=i+1;jsize;j+)L-dataj-1= L-dataj;Lsize-;elsefor(j= Lsize;ji;j-)L-dataj= L-dataj-1;L-datai=x; Lsiz
8、e+;2已知有如下定义typedef struct LNode int data;struct LNode *next;*LinkList, LNode ;则下列算法的功能是ListList Demo(LinkList L)ListNode *Q,*P;if (L&L-next)Q=L;L=L-next;P=L;while(P-next) P=P-next;P-next=Q;Q-next=NULL;return L;3请写出下列程序段的输出结果。SeqStack S; /初始化栈 Schar x,y;x=L; y=O;Push(S,x); Push(S,x);Push(S,y); x=Pop(
9、S);Push(S,E); Push(S,x);x=Pop(S); Push(S,H);while(!StackEmpty(S)y=Pop(S); putchar(y);putchar(x); 得分五、算法设计题（共 25 分）1.用顺序表实现：有 10 本图书，每本图书的数据有：书号，价格；设计算法 input( )从键盘上输入 10 本图书的数据；设计算法 average( )计算 10 本书的平均价格并输出。 (14 分)# define MaxSize 100typedef struct int id;float price;book ; typedef book DataType;typedef sturctDataType listMaxSize;int size;SeqList;void input(SeqList * L)void average( SeqList L)2. 将一个带头结点的单链表就地逆序。 （11 分）
