数据结构测验12

《数据结构测验12》由会员分享，可在线阅读，更多相关《数据结构测验12（8页珍藏版）》请在装配图网上搜索。

1、12 级数据结构测验（一）一、单选题1. 数据在计算机内存中的表示是指。A）数据的存储结构B）数据元素C）数据的逻辑结构D）数据元素之间的关系2线性表的物理结构可以分为两类。A）内部结构和外部结构B）紧凑结构和非紧凑结构C）线性结构和非线性结构D）链式结构和非链式结构3在存储数据时，通常不仅要存储数据元素的值，而且还要存储。A）数据的处理方法B）数据元素的类型C）数据元素之间的关系D）数据的存储方法4计算机中算法指的是解决某一问题的有限运算序列，它具备输入、输出、 5 个特征。确定性可行性有穷性可移植性可读性A）B）C）D）5在单链表中增加头结点的目的是。A）使单链表至少有一个结点B）标志表中

2、首结点的位置C）便于插入删除运算的实现D）说明单链表是线性表的链式存储实现6. 设rear是指向非空的带头结点的单循环链表链尾结点的指针，若要删除链表第一个结点，则应该执行。A）s=rear; rear=rear-next; free（s）;B）rear=rear-next; free（rear）;C）rear二rear-next-next; free（rear）;D）s=rear-next-next;rear-next-next二s-next; frre（s）;7. 对于链队列，在进行删除操作时。A）仅修改头指针监仅修改尾指针C）头、尾指针都要修改D）头、尾指针可能都要修改8在双向链表中删除

3、p所指结点的前驱结点（存在）的操作为A）p-prior-next=p-next; p-next-prior=p-prior;B）p-prior二p-prior-prior; p-prior-prior-next二p;C）p-prior-prior-next二p; p-prior=p-prior-prior;D）p-next-next-prior二p;p-next二p-next -next;9.在具有n个顺序存储单元的循环队列中，队满时共有个元素。A） nB） n-1C） n+1D） n+210在长度为n （n1）的单链表上，在值为e的结点后面插入一个新结点的 算法的时间复杂度为。A) O (n

4、)B) O (1)C) O (n2)D) O (nlogn)11. 判断一个表达式中左右括号是否成对出现的算法，采用_数据结构最好。A)顺序表B)单链表0|顺序栈D)链队列12. 经过以下队列运算后，队头的元素是。InitQueue(qu) ； enQueue(qu，b) ；enQueue(qu，d) ， enQueue(qu, c ), deQueue(qu)；A) d B) bC) c D) d13. 算法的时间复杂度与有关。A)处理器个数B)计算机硬件性能C)问题规模D)程序设计语言14表达式(a+b) *(b+c)/f的后缀表达式为。A) abbcf+*/B) ab+bc+*f/C)

5、ab+*bd+f/D) /*+abbcf15.在长度为n的顺序表的第i(1WiWn)个位置上删除一个元素需要移动 个元素。A) n-i+1B)| n-iC) iD) i-116顺序栈S中元素个数是。A) S.to p-1-S.baseB) S.to p-S.base+1C) S.top+S.baseD)|S. top-S.base17.循环队列qu的队满条件是。A) (Q.rear+1) %MAXQSIZE =(Q.front+1)% MAXQSIZEB) (Q.rear+1) % MAXQSIZE =Q.front+1C) (Q.rear+1) % MAXQSIZE =Q.frontD) Q

6、.rear= Q.front18设n个元素进栈序列是p1, p2, p3,，pn,其输出序列是1, 2, 3, n,若 pn=1，则 pi (1in-1)的值是。A) n-i+1B) n-iC) iD)有多种可能19. 插入和删除都在表的两端进行的线性表是。A)双端队列B)栈C)顺序表D)双向链表20. 栈的操作原则是。A)先进先出|B)后进先出C)只能进行插入D)只能进行删除二、填写物理结构和基本操作1. ListDelete用于删除顺序表中第i个元素。#define LIST_INIT_SIZE 100 线性表存储空间的初始分配 #define LISTINCREMENT 10 线性表存储

7、空间的分配增量 typedef struct ElemType 1*elem _;int_2 leng th;int3listsize ；SqList;Status ListDelete(SqList &L,int i,ElemType &e) /*初始条件：顺序线性表L已存在，lWiWListLength(L) */ /*操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 */ ElemType *p,*q;if(iL.length) return ERROR;p=4 L.elem+iT 或&(Lelemi-l);e=*p;q=5 L.elem+L.length-l ;for(;

8、 pnext=NULL;void Pop(LinkStack &s,ElemType &e) SNode *p;if(9 s-next)printf(目前此栈是空栈，此次出栈失败了！ n); else p=s-next; ; ; free(p);prin tf(此次出栈成功，出栈元素是:dn,e);3集合并集运算void jiaoji(List La,List Lb,List &Lc) /线性表La、Lb分别表示集合A、B, C=AQBint i,La_len,Lb_len,k;ElemType e;InitList(Lc);k=1;La_len=ListLength(La);Lb_len=L

9、istLength(Lb);/求线性表的长度for (i=l;i二12 Lb len_;i+) 13 Get Elem_Sq(Lb,i,e);_;if(LocateElem_Sq(La,e,equal)14 Listlnsert_Sq(Lc,k+,e)_;/jiaoji三、简答题1处理数学模型为线性表的问题，何时选用顺序表？何时选用单链表？ 2在单循环链表中仅设尾指针比仅设头指针好吗？3. 设栈s和队列q的初始状态都为空，元素a, b, c, d, e和f依次通过栈s, 一个元素出栈后即进入队列q,若6个元素出队的序列是bdfeca，则栈s的容 量至少应该存多少个元素?4. 分析以下算法的时间

10、复杂性(1) 设 La.length 为 na, Lb.length 为 nbvoid MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc) 已知单链线性表La和Lb的元素按值非递减排列归并La和Lb得到新的单链线性表Lc,Lc的元素也按值非递减排列 pa = La-next; pb = Lb-next;Lc = pc = La;用La的头结点作为Lc的头结点while( pa&pb )if (pa-data= pb-data) pc-next = pa;pc = pa; pa = pa-next;elsepc-next = pb; pc

11、= pb; pb = pb-next;pc-next = pa ? pa:pb;插入剩余段free(Lb);释放Lb的结点 MergeList_L(2)int s=0;for(i=0; i=n; i+) for(j=0; j=i; j+) for(k=0; knext10e二*p11s-next二p-next12Lb_len13Get Elem_Sq(Lb,i,e);14Lis tl nser t_ Sq(Lc,k+,e)注：2-3 可以互换10-11 可以互换三、简答题1经常进行查询、随即访问的操作可以选用顺序表 经常进行插入删除操作适宜用单链表 2若经常在最后一个结点后面插入结点或把两个链

12、表合并成一个链表适宜用 带尾指针的单循环链表，否则没有优势344(1) T(na,nb)=O(na+nb)(2) T(n)=O(n3)四、1#define MAXQSIZE 100最大队列长度typedef structQElemType*base;初始化的动态分配存储空间intfront;头指针,若队列不空,指向队列头元素intrear;尾指针,若队列不空,指向队列尾元素的下一个位置intfull;/队列是否满的标识SqQueue;Statue InitQueue(SqQueue &Q)构造一个空队列QQ.base = (QElemType *)malloc(MAXQSIZE * sizeo

13、f(QElemType);if (!Q.base) exit(OVERFLOW); 存储分配失败Q.front = Q.rear = 0;Q.full=0;/不满return OK;Status EnQueue(SqQueue &Q,QElemType e)插入元素e为Q的新的队尾元素if(Q.full=1)return ERROR;队列满Q.baseQ.rear = e;Q.rear = (Q.rear+1)% MAXQSIZE;if(Q.rear = Q.front) Q.full=1;return OK;2Status PriorElem(LinkList L, ElemType cur_e, ElemType &pre_e) /L 为带头结点的单链表的头指针 ,p=L-next; pre_e=L-data;while(p)if(p-data=cur_e &p!=L-next)return OK; pre_e=p-data ； p=p-next;return ERROR;