《算法与数据结构》过程考试样卷

《《算法与数据结构》过程考试样卷》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《算法与数据结构》课程第1次过程考试一、选择题（共30分。每小题3分。）()01、算法分析的目的是：__。A)找出数据结构的合理性B)研究算法中的输入和输出的关系C)分析算法的效率以求改进D)分析算法的易懂性和文档性()02、线性表的常用操作是存取第i个元素及其前趋的值，则采用__存储方式最省时间。A)单向链表B)双向链表C)单向循环链表D)顺序表()03、链表不具有的特点是__。A)可随机访问任一元素B)插入删除操作不需要移动元素C)不必事先估算存储空间D)所需空间与线性表长度成正比()04、在单向链表的指针p所指结点后插入结点*s(*p不是尾结点)，则应执行__操

2、作。A)s->next=p;p->next=s;B)s-next=p->next;p->next=s;C)s-next=p->next;p=s;D)p->next=s;s->next=p;()05、在有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较__个结点。A)nB)n/2C)(n-1)/2D)(n+1)/2()06、在具有n个结点的有序单链表中插入一个新结点，并仍然有序的时间复杂度为__。A)O(1)B)O(n)C)O()D)O()()07、设有一个栈，元素依次进栈顺序为A、B、C、D、E。下面__是不可能的出栈序列。A)ABCDEB)B

3、CDEAC)EABCDD)EDCBA()08、数组Q[n]用来表示一个循环队列，f为当前队列头元素的前一位置，r为队尾元素的位置，假定队列中元素的个数小于n，计算队列中元素的公式为__。A)r-fB)(n+f-r)%nC)n+r-fD)(n+r-f)%n()09、队列的入队顺序是a,b,c,d，则离队顺序是__。A)adcbB)abcdC)dcbaD)cbda()10、串是一种特殊的线性表，其特殊性体现在__。A)只有顺序存储结构B)数据元素是一个字符C)数据元素是整个串D)串操作受限只能为子串操作二、填空题（共14分。每空2分。）11、数据在计算机中的存储可以分为(

4、)存储结构和()存储结构两大类。12、在长度为n的顺序表中，插入一个新元素平均需要移动表中()个元素，删除一个元素平均需要移动()个元素。13、队列只能在()位置进行插入操作和()位置进行删除元素的操作。14、若两个串的长度相等且对应位置上的字符也相等，则称两个串()。11、一个算法的效率可分为()效率和()效率。12、在长度为n的顺序表中，表头插入一个新元素的时间复杂度为()，表尾插入一个新元素的时间复杂度为()。13、栈是一种只能在()位置进行插入和删除元素的线性结构。14、串长度为0的串称为()，只包含空格的串称为(）。三、简单操作题(共24分。)15、写出下列

5、算法的时间复杂度（本小题4分）A）for(i=0;i

6、Q,d);}}18、完成稀疏矩阵的三元组表操作。（本小题5分）A）下面是4*4稀疏矩阵转置后的三元组表，画出原稀疏矩阵。ije123312331435B）写出下面矩阵的三元组表19、请写出顺序表和单向链表的类型定义。（本小题6分）四、程序填空（共18分。每空3分。）20、程序填空1A)逆序建立链表voidCreateList_1(LinkList*L,intn){L=(LinkList)malloc(sizeof(LNode));for(i=1;i<=n;i++){p=(LinkList)malloc(sizeof(LNode));scanf(&p->data);}}

7、B)顺序建立链表voidCreateList_2(LinkList*L,intn){L=(LinkList)malloc(sizeof(LNode));q=L;for(i=1;i<=n;i++){p=(LinkList)malloc(sizeof(LNode));scanf(&p->data);p->next=NULL;}}21、程序填空2A）链表的插入算法ListInsert_L(LinkListL,inti,ElemTypee)//在带头结点的单链表L中第i个位置之前插入元素e。{p=L;j=0;while(p&&jnext