《数据结构》习题集
第一章 序论
思考题
1.1 简述下列术 语:数据、数据元素、数据对象、数据结构、存储结构、数据类型、抽象数据类型
作业题
1.2 设有数据结构(D,R),其中
    D={d1, d2, d3, d4 }
    R={r1, r2}
    r1={ <d1, d2>, <d2, d3>, <d3, d4>, <d1, d4>, <d4, d2>, <d4, d1> }
    r2={ (d1, d2), (d1, d3), (d1, d4), (d2, d4), (d2, d3) }
试绘出其逻辑结构示意图。
1.3 设n是正整数。试写出下列程序段中用记号“”标注的语句的频度:
(1)    i=1; k=0;
        while(i<=n-1) {
            k+=10*i;
            i++;
        }
(2)    i=1; k=0;
        do {
            k+=10*i;
            i++;
        }while(i<=n-1)
(3)     i=1; k=0;
        do {
            k+ = 10*i; i++;
        }while(i==n);
(4)        i=1; j=0;
        while(i+j≤n) {
        △    if(i<j) i++; else j++;
        }
(5)        x=n; y=0; //n是不小于1的常数
        while(x>=(y+1)*(y+1)){
        △    y++;
        }
(6)        x=91; y=100;
        while ( y>0 ) {
            if(x>100) { x-=10; y--; }
            else  x++ ;
        }
(7)        for( i=0; i<n; i++)
            for( j=i; j<n; j++)
                for( k=j; k<n; k++)
                    x+=2;
1.4 试写一算法,自大至小依次输出顺序读入的三个整数X,Y和Z的值。
1.5 已知k阶斐波那契序列的定义为:
f0=0, f1=0,……, fk-2=0, fk-1=1;
fn= fn-1+ fn-2+……+ fn-k,    n=k,k+1,……
试编写求k阶斐波那契序列的第m项值的函数算法,k和m均以值调用的形式在函数参数表中出现。
第二章 线性表
思考题
2.1 描述以下三个概念的区别:头指针、头结点、首元结点。
2.2 描述以下几个概念:顺序存储结构、链式存储结构、顺序表、有序表。
作业题
2.3    已知顺序表La中数据元素按非递减有序排列。试写一个算法,将元素x插到La的合适位置上,保持该表的有序性。
2.4    已知单链表La中数据元素按非递减有序排列。按两种不同情况,分别写出算法,将元素x插到La的合适位置上,保持该表的有序性:(1)La带头结点;(2)La不带头结点。
2.5    试写一个算法,实现顺序表的就地逆置,即在原表的存储空间将线性表(a1,a2, ..., an-1,an逆置为(an,an-1, ..., a2,a1)
2.6    试写一个算法,对带头结点的单链表实现就地逆置。
2.7    已知线性表L采用顺序存储结构存放。对两种不同情况分别写出算法,删除L中值相同的多余元素,使得L中没有重复元素:(1)L中数据元素无序排列;(2)L中数据元素非递减有序排列。
2.8    将2.7题中L的存储结构改为单链表,写出相应的实现算法。
2.9 设有两个非递减有序的单链表A和B。请写出算法,将A和B“就地”归并成一个按元素值非递增有序的单链表C。
2.10 设有一个长度大于1的单向循环链表,表中既无头结点,也无头指针,s为指向表中某个结点的指针,如图2-1所示。试编写一个算法,删除链表中指针s所指结点的直接前驱。
2.11 已知线性表用带头结点的单链表表示,表中结点由三类字符组成:字母、数字和其他字符。试编写算法,将该线性链表分割成三个循环单链表,每个循环单链表中均只含有一类字符。
2.12 已知线性表用顺序存储结构表示,表中数据元素为n个正整数。试写一算法,分离该表中的奇数和偶数,使得所有奇数集中放在左侧,偶数集中放在右侧。要求:(1)不借助辅助数组;(2)时间复杂度为O(n)
2.13 设以带头结点的双向循环链表表示的线性表L=(a1,a2,a3,...,an)。试写一时间复杂度为O(n)的算法,将L改造为L=(a1,a3,...,an,...,a4,a2)
第三章 栈和队列
思考题
3.1 简述栈和线性表的差别。
3.2 数据结构与算法题库如果进栈序列为A、BCD,写出所有可能的出栈序列。
3.3 简述栈和队列的相同点和差异。
3.4 已知栈S中存放了8个数据元素,自栈底至栈顶依次为(1,2,3,4,5,6,7,8)。(1)写出在执行了函数调用algo1(S)后,S中的元素序列。
(2)在(1)的基础上,又执行了函数调用algo2(S,5),写出此时S中的元素序列。
void algo1(Stack &S){
    int a[10], i, n=0;
    while(!StackEmpty(S)){ n++; Pop(S, a[n]); }
    for(i=1; i<=n; i++) Push(S, a[i]);
}
void algo2(Stack &S, int e){
    Stack T;
    int d;
    InitStack(T);
    while(!EmptyStack(S)){
      Pop(S,d);
      if(d!=e) Push(T,d);
    }
    while(!StackEmpty(T)){
      Pop(T,d);
      Push(S,d);
    }
}
3.5已知队列Q中自队头至队尾依次存放着(1,2,3,4,5,6,7,8)。写出在执行了函数调用algo3(Q)后,Q中的元素序列。
void algo3(Queue &Q){
    Stack S;
    int d;
    InitStack(S);
    while(!QueueEmpty(Q)){
        DeQueue(Q,d); Push(S,d);
    }
    while(!StackEmpty(S)){
        Pop(S,d); EnQueue(Q,d);
    }
}
作业题:
3.6 试写一个算法,识别依次读入的一个以@为结束符的字符序列是否为形如“序列1&序列2”模式的字符序列。其中,序列1和序列2中都不包含字符‘&,且序列2是序列1的逆序。例如,“
a+b&b+a”是属于该模式的字符序列,而“1+3&3-1则不是。

版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198,我们将在24小时内删除。