N1数据结构答案.doc

算法与数据结构课程第1次过程考试学号： 姓名： 成绩：一、选择题（共30分。每小题3分。）( D )01、计算机算法指的是_。 A) 计算方法 B) 排序方法 C) 调度方法 D) 解决问题的有限运算序列( D )02、数据的逻辑结构被形式地定义为B=(K,R)，其中K是数据元素的有限集合，R是K上的_有限集合。 A) 操作 B) 映像 C) 存储 D) 关系( A )03、线性表L在 情况下适用于使用链式结构实现。 A) 不断对L进行删除插入 B) 经常修改L中的结点值 C) L中含有大量的结点 D) L中结点结构复杂( A )04、在单循环链表中指针p指向结点A，若要删除A之后的结点(存在)，则其中指针的链接操作为_。 A)p-next=p-next-next B)p=p-next C)p=p-next-next D)next=p( C )05、对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为_。 A) O(n) O(n) B) O(n) O(1) C) O(1) O(n) D) O(1) O(1)( B )06、一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是_。 A) 2 3 4 1 5 B) 5 4 1 3 2 C) 2 3 1 4 5 D) 1 5 4 3 2 ( B )07、如果以链表作为栈的存储结构，则退栈操作时必须判别_。 A) 栈是否为满 B) 是否为空 C) 栈的元素类型 D) 不作任何判别( C )08、数组Qn用来表示一个循环队列，f为当前队列头元素的前一位置，r为队尾元素的位置，假定队列中元素的个数小于n，计算队列中元素的公式为_。 A) r-f B) (n+f-r)%n C) (n+r-f)%n D) n+r-f( C )09、S为长度为n的字符串，其字符各不相同，则S的互异非平凡子串(非空且不同于S本身)个数为_。 A) 2n-1 B) n(n+1)/2 C) n(n+1)/2-1 D) n(n-1)/2 E) n(n-1)/2-1( C )10、n*n的对称方阵，若以行或列为主序放入内存中，则容量为_。 A) n*n B) n*n/2 C) n*(n+1)/2 D) n*(n-1)/2二、填空题（共16分。每空2分。）11、数据在计算机中的存储可以分为( 顺序 )存储结构和( 链式 )存储结构两大类。12、栈的操作特点是( 后进先出 )，队列的特点是只能在队首进行( 删除 )操作，队尾进行( 插入 )操作。13、循环队列设计时，要解决循环引用问题，还要解决( 队空和队满 )的判断问题。14、若两个串的长度相等且对应位置上的字符也相等，则称两个串( 相等 )。15、稀疏矩阵的稀疏因子为0.05，若采用三元组方式存储，且三元组数组中最多存储20个元素，则该三元组可表示的最大二维方阵的维界是( 20 )。三、简单操作题(共12分。)16、写出下面程序的功能(4分)void delete(Linklist *L) p=L; while (p-next!=NULL) m=p-next-data; q=p; while (q-next!=NULL) if (q-next-data=m) r=q-next; q-next=r-next; free(r); q=q-next; p=p-next; 答案：删除重复元素17、写出下面程序运行后的结果(4分)void demo(Queue &Q)Stack S; int d; InitStack(S); while(!QueueEmpty(Q) DeQueue(Q,d); if (d%2=0) Push(S,d); while(!StackEmpty(S) Pop(S,d); EnQueue (Q,d);若队列中的数据元素为1,2,3,4,5,6,7,8，则执行demo后，队列中的数据元素为： 8 6 4 2 18、写出下面稀疏矩阵“转置”后的三元组表。（4分）i j e1 2 33 1 23 4 5四、程序填空（共24分。每空3分。）19、按输入顺序建立链表void CreateList_2(LinkList *L, int n) L=(LinkList)malloc(sizeof(LNode); L-next=NULL; q=L; for(i=1; idata); p-next=NULL; q-next=p; q=p; 20、在带头结点链表的第i个位置插入元素ListInsert_L(LinkList L, int i, ElemType e) p=L; j=0; while(p&jnext; +j; if(!p|ji-1) return ERROR; s=(LinkList)malloc(sizeof(LNode); s-data=e; s-next=p-next; p-next=s;21、将十进制数据转换为八进制数据void conversion() InitStack(&S); printf(nDEC number:); scanf(%d,N); while(N) Push(&S,N%8); N=N/8; while(!StackEmpty(S) Pop(S,e); printf(%d,e);22、在串中字位子串int index(SString S, SString T, int pos) if (pos0) n=StrLength(S); m=StrLength(T); i=pos; while (i=n-m+1) SubString(sub,S,i,m); if (StrCompare(sub,T)!=0) i+; else return i; return 0; 五、算法设计题（共18分。）23、已知线性表的存储结构如下，设计算法，完成线性表的逆置操作。/* 顺序表的存储结构 */typedef struct ElemType *elem;int length; SqList;/* 链表的存储结构 */typedef struct LNodeElemType data;struct LNode *next; LNode,*LinkList;1) 设计算法void reverse1(SqList &L)，完成顺序表中数据元素的逆置。2) 设计算法void reverse2(LinkList &L)，完成无头结点单链表的就地逆置，即要求利用原结点