数据结构习题02360

-期中测验一、单项选择题（每小题2分，共30分）【得分： 】1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.1、设计一个判别表达式中左、右括号是否配对出现的算法，采用( )数据结构最佳。A. 线性表的顺序存储结构 B. 栈C. 队列 D. 线性表的链式存储结构2、以下算法的时间复杂度为( )。void fun(int n)int i=l;while (inext=NULL C. head-next=head D. head!=NULL4. 在一个具有n个单元的顺序栈中，假设栈底是存储地址的低端，现以top作为栈顶指针（指向栈顶元素的下一个位置），当进行出栈操作时，假定栈非空，top的变化是( )。A. top=top+1 B. top=top-1 C. top不变 D. top不确定5. 一个栈的入栈序列为a，b，c，d则出栈序列不可能的是( )。A. a，b，c，d B、c，b，a，d C. d，c，b，a D、d，b，c，a6、二维数组SA中，每个元素的长度为3个字节，行下标I从0到7，列下标J从0到9，从首地址SA开始连续存放在存储器内，该数组按行优先存放时，元素A68的起始地址为（ ）。A. SA+210 B. SA+171 C. SA+204 D. 以上都不对7、以下关于单链表的叙述中，错误的是（ ）。A.在单链表中插入一个节点必须先找到其前趋节点B.在单链表中删除一个节点必须先找到其前趋节点C.在单链表中只能通过节点的next指针向后查找节点D.在单链表中查找第i个节点的时间复杂度为0(1)8. 链表不具有的特点是（ ）。A. 可随机访问任一元素B. 插入删除不需要移动元素C. 不必事先估计存储空间D. 所需空间与线性表长度成正比9. 在一个单链表中，已知q是p的前趋结点，若q和p之间插入结点s，则执行（ ）。. s-next=p-next; p-next=s; . p-next=s-next; s-next=p; . q-next=s; s-next=p; . p-next=s; s-next=q;10. 若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省时间。A. 顺序表 B. 单链表 C. 双向链表 D. 循环链表11、下面关于串的的叙述中，哪一个是不正确的？（ ）A串是字符的有限序列 B空串是由空格构成的串C模式匹配是串的一种重要运算 D串既可以采用顺序存储，也可以采用链式存储12、循环链表主要优点是（ ）。A. 不再需要头指针了B. 已知某个结点的位置后，能够容易找到它的直接前趋C. 在进行插入、删除运算时，能更好地保证链表不断开D. 从表中任一结点出发都能扫描到整个链表13、与单链表相比，双链表的优点之一是（ ）。 A.插入、删除操作更简单 B.可以进行随机访问 C.可以省略表头指针或表尾指针 D.前后访问相邻节点更灵活14.循环队列SQ采用数组空间SQ.base0,n-1存放其元素值，已知其头尾指针分别是front和rear，则判定此循环队列为空和为满的条件分别是（ ）A. Q.front!=Q.rear, Q.front=Q.rear B. Q.front=Q.rear , Q.front!=Q.rear C.Q.front=Q.rear, Q.front=(Q.rear+1)%n D.Q.front=Q.rear , Q.front!=(Q.rear+1)%n15. 利用栈求表达式的值时，设立操作数栈OPND，假设OPND只有两个存储单元，在下列表达式中，不发生溢出的是（ ）。A. A-B*(C-D)B. (A-B)*C-DC. (A-B*C)-DD. (A-B)*(C-D)二、填空题（每空2分，共10分 ）【得分： 】1. 若一个算法中的语句频度之和为T（n）=3n+n*log2n+4，则算法的时间复杂度为 _n_ _。2.对于n阶对称矩阵，进行压缩存储，如果以行序或列序放入一维数组中，则需要 n*(n+1)/2 个存储单元。3在非空双向循环链表中，在结点q的前面插入结点p的过程如下：p-prior=q-prior; q-prior-next=p; p-next=q; q-prior=p ;4. 将一个下三角矩阵A1.50,1.50按行优先存入一维数组B1.n中，A中元素A30,20在B数组中的位置为 454 。5. 设S=I am a Student，T=good,则ConCat(T,SubStr(S,7,8)= S 。三、简答题（每题6分，共30分 ）【得分： 】1. 假设Q0，9是一个非循环线性队列，初始状态为front=rear=0，画出做完下列操作后队列的头尾指针的状态变化情况，如果不能入队，请指出其元素，并说明理由。 d,e,b,g,h入队 d,e出队 I,j,k,l,m入队 b出队 n,o,p,q,r入队。答：ije1221393133634345286116472. 已知稀疏矩阵如下所以，请写出该稀疏矩阵对应的三元组表示和该矩阵转置矩阵的三元组表示。答：稀疏矩阵对应的三元组表示为(i,j,a(i,j)。右表为该矩阵的三元组表:3设有多项式a(x)=9+8x+9x4+5x10，b(x)=-2x+22x7-5x10，c(x)=a(x)+b(x)。用单链表给出a(x)、b(x)和c(x)的存储表示。答：用单链表表示多项式，除指针域外需设置两个数据域，一个用来存储系数，一个 用来存储指数。4.若较频繁地对一个线性表进行插入和删除操作，该线性表宜采用哪种存储结构？为什么？答：采用链式存储结构，它根据实际需要申请内存空间，而当不需要时又可以将不用节点空间返还给系统。在链式存储结构中插入和删除操作不需要移动元素。5对于堆栈，给出三个输入项A，B，C，如果输入项序列为ABC，试给出全部可能的输出序列，并写出每种序列对应的操作。例如：A进B进C进C出B出A出，产生的序列为CBA。答：ABC,CAB,BCA,ACB,BAC。四、算法阅读题（每空2分，共 16分） 1以下为头插法建立单链表的算法，请在下划线处填上适当的语句。void CreateList_L(LinkList &L, int n) /输入n个元素的值，建立带头结点的单链表L /每次都将新结点(由p指向)插入到头结点的后面。 L=(LinkList)malloc(sizeof(LNode); L-next=NULL ; /先建立一个带头结点的单链表 for(i=n; i0; -i) p =(LinkList)malloc(sizeof(LNode);scanf(&p data); p-next=L-next ; L next=p; / CreateList_L2已知循环队列存储结构的定义，以下运算实现在循环队列上的入队列和出队列，请在下划线处用适当的语句予以填充。#define MAXQSIZE 100 /最大队列长度typedef struct QElemType *base; /初始化的动态分配存储空间 int front; /头指针,若队列不空,指向队列头元素. int rear; /尾指针,若队列不空,指向队列尾元素的下一个位置.SqQueue; Status EnQueue(SqQueue &Q,QElemType e)/入队 if(_Q.front=(Q.rear+1)%MAXQSIZE_) return ERROR;/队列满 Q.baseQ.rear=e; _Q.rear=(Q.rear+1)%MAXQSIZE_ return OK;/EnQueueStatus DeQueue (LinkQueue &Q,QElemType &e)/出队 if(_Q.front=Q.rear_) return ERROR;/队列空 e=Q.baseQ.front; _Q.front=(Q.front+1)%MAXQSIZE_; return OK;/DeQueue3以下为带头结点的单链表的定位运算，分析算法，请在下划线处填上适当的语句。int LocateElem(LinkList head,DataType x)/*求表head中第一个值等于x的结点的序号。不存在这种结点时结果为0*/p=head-next;j=1;while(p!=NULL&jnext_;j+;if(p&p-data=x) return(j);elsereturn(0);五、算法设计题（1小题，共14分）【得分： 】1已知栈的基本操作函数：int InitStack(SqStack *S); /构造空栈int StackEmpty(SqStack *S);/判断栈空int Push(SqStack *S,ElemType e);/入栈int Pop(SqStack *S,ElemType *e);/出栈试写一算法conversion实现十进制数转换为十六进制数，利用上面的基本操作来实现。答：/数制转换 #define _CRT_SECURE_NO_WARNINGS #include #include #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef int Status; typedef int SElemType; #define STACK_INIT_SIZE 10 #define STACK_INCREMENT 2 struct SqStack SElemType *base; SElemType *top; int stacksize; ; void InitStack(SqStack &S) S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType); if(!S.base) exit(OVERFLOW); S.top=S.base; S.stacksize=STACK_INIT_SIZE; Status StackEmpty(SqStack S) if(S.top=S.base) return TRUE; else return FALSE; Status Push(SqStack &S,SElemType e) if(S.top-S.base=S.stacksize) S.base=(SElemType*)realloc(S.base, (S.stacksize+STACK_INCREMENT)* sizeof(SElemType); if(!S.base) exit(OVERFLOW); S.top=S.base+S.stacksize; S.stacksize+=STACK_INCREMENT; *(S.top)+=e; return OK; Status Pop(SqStack &S,SElemType &e) if(S.top=S.base) return ERROR; e=*-S.top; return OK; void conversion(int n,int m) SqStack S; SElemType e; InitStack(S); while(n) Push(S,n%m); n=n/m; while(!StackEmpty(S) Pop(S,e); printf(%