数据结构习题.docxVIP

习题一一、填空题1. 算法具有有穷性、 确定性 、 可行性 、 输入 和输出五大特征。2. 数据结构的内容包括以下三个方面： 数据元素 、 数据关系 和运算集合。3. 数据结构的存储结构分为 顺序、 链式 、索引、散列。4. 评价算法性能的标准主要从算法执行 时间 和 空间 两方面考虑。5. 在线性结构、树形结构和图状结构中，数据元素之间分别存在着 1对1 、 1对多 和 多对多 关系。二、分析题设n为整数，分析下列程序段中，用*标明的语句的语句频度及时间复杂度。for(n =1;n=10;n++) *s=s+n; (2) for(i =1;i=n;i++) *s=s+n; (3) for(i =1;i=n;i++) for(j=1;j=n;j++) *s=s+n (4) for(i =1;i=n;i++) for(j=1;j=i ;j++) *s=s+n;（5）for(i =1;i=n;i++) for(j=1;j=n;j++) { c[i][j]=0; for(k=1;k=n;k++) *c[i][j]=c[i][j]+a[i][k]*b[k][j]; }习题二填空题在顺序表中，逻辑上相邻的元素，其物理位置上 一定 相邻。在单链表中，逻辑上相邻的元素，其物理位置上 不一定 相邻。设单链表中，指针p指向结点s，若要删除s之后的结点（若存在），则需修改指针的操作为 P=s-next;s-next=s-next-next;free(p); 。在一个长度为n的顺序表中，如果要删除第i个元素，需移动 n-i+1 个元素。选择题某线性表中最常用的操作是存取序号为i的元素和在最后进插入和删除运算，则采用（ C ）存储方式的时间性能最好。双向链表 B.双向顺环链表 C.顺序表 D.单向顺环链表在一个单链表中，已知q结点是p结点的前驱结点，若在p和q之间插入s结点，则需执行（ C ）。s-next=p-next;p-next=sB.p-next=s-next;s-next=pC.q-next=s;s-next=pD.p-next=s;s-next=q带头结点的单链表为空的判定条件是（ B ）。L=NULL B.L-next=NULL C.L-next=head D.L!=NULL某线性表中最常用的操作是存取第i元素及其前驱结点的值，则采用（ C ）存储方式能节省时间。A双向链表 B.双向循环环链表 C.顺序表 D.单向循环环链表已知一个带头结点的非空循环单链表，其尾指针是R，则其首元素结点的地址为( D )。R-next B.*(r-next-next) C.(r-next-next) D.R-next-next编程题6.试将入口为head的有序单链表，按所给关键字k分成两个循环链表。其中，比k小的所有结点组成入口为h1的循环链表，比k大的所有结点组成入口为h2的循环链表。对于单链表，写出下列操作的算法。根据一维数组建立一个单链表，使单链表中元素的顺序与数组的次序相同。统计单链表中值在x~y之间的所有结点个数。删除单链表中第k个结点开始连续的j个结点。将该单链表分解为两个单链表，使其中一个单链表中仅含有奇数，另一个单链表中仅含有偶数。将另一个已经存在的单链表插入到该链表的第k个结点之后。将单链表中的所有元素排成一个有序序列。习题三分析题写出下列程序段的输出结果 void main(){ stack s; char x,y; stackinit(s); \\构造一个空栈s x=‘c’; y=‘k’; push(s,x); \\将新元素x插入到栈s中 push(s,‘a’); push(s,y); pop(s,x); \\从栈s中删除顶元x push(s,‘t’); push(s,x); pop(s,‘s’); push(s,x); \\判断栈s是否为空，若为空，返回1，否则返回0 While(!stackempty(s)) { pop(s,y); printf(y); }printf(x);}写出以下程序段的输出结果。 void main(){queue q;char x=‘e’;char y=‘c’;queinit(q); //构造一个空队列qenque(q,‘h’); //将元素h到队q的尾部enque(q,‘r’);enque(q,y);deque(q,x); //删除队q的队首元素xenque(q,x);deque(q,x);enque(q,‘a’); while(! queempty(q))//当队q非空{ deque(q,y); rintf(y);}printf(x);}习题四一、填空题1. 串是一种特殊的线性表，其特殊性表现在 。2. 串的