软件技术基础复习思考题PPT学习教案

1、会计学1 软件技术基础复习思考题软件技术基础复习思考题 2/125 软件技术基础电子教案 第1页/共125页 3/125 一、名词解释一、名词解释 数据，数据元素，逻辑结构，存储结构，线性结构，非 线性结构，顺序存储结构，链式存储结构，索引存储结构， 散列存储结构，算法，时间复杂度 二、填空题二、填空题 1从某种意义上说，数据、数据元素和数据项反映了数 据组织的三个层次，数据可由若干个_构成，数据元 素可由若干个_构成。 2从逻辑关系上讲，数据结构主要分为两大类，它们是 _和_。 第2页/共125页 4/125 3把逻辑上相邻的数据元素存储在物理上相邻的存储 单元中的存储结构是_。 4通常从_

2、、_、_等几方面评价 算法的质量。 5常见时间复杂性的量级有：常数阶O(_)、对数阶 O(_)、线性阶O (_)、平方阶O(_)和指数阶 O(_)。 6在一般情况下，一个算法的时间复杂性是_ 的函数。 7一个算法的时空性能是指该算法的_和 _，前者是算法包含的_，后者是算法需要的 _。 第3页/共125页 5/125 三、问答题三、问答题 分析下列程序段的时间复杂度。 (1) i=1;k=0; while(in) k=k+10*i;i+; (2) i=1;j=0; while(i+jj) j+; else i+; 第4页/共125页 6/125 线性表线性表 一、名词解释一、名词解释 线性结构

3、，非线性结构，顺序存储结构，链式存储结构， 存储密度 二、填空题二、填空题 1为了便于讨论，有时将含n(n0)个结点的线性结构表 示成(a1，a2,，an)，其中每个ai代表一个_。a1称为 _结点，an称为_结点，i称为ai在线性表中的 _。对于任意一对相邻结点ai、ai+1(1in), ai称为ai+1的 直接_，ai+1称为ai的直接_。 第5页/共125页 7/125 2线性结构的基本特征是：若至少含有一个结点，则 除开始结点没有直接_外，其他结点有且仅有一个直接 _；除终端结点没有直接_外，其它结点有且仅有 一个直接_。 3线性表的逻辑结构是_结构。其所含结点的个数 称为线性表的_，

4、简称_。 4表长为0的线性表称为_。 5顺序表的特点是_。 6假定顺序表的每个datatype类型的结点占用k(k1)个内 存单元，b是顺序表的第一个存储结点的第一个单元的内存地 址，那么第i个结点ai的存储地址为_。 第6页/共125页 8/125 7以下为顺序表的删除运算，分析算法，请在_处填 上正确的语句。 void delete_sqlist(sqlist*L,int i) /删除顺序表L中的第i-1个 位置上的结点 if(iL-last) error(“非法位置”)； for(j=i+1;j=L-last;j+) _; L-last=L-last-1; 8为了便于实现各种运算，通常在

5、单链表的第一个结点 之前增设一个类型相同的结点，称为_，其它结点称 为_。 第7页/共125页 9/125 9以下是求带头结点的单链表长度的运算，分析算法，请 在_处填上正确的语句。 int length_linklist(linklist*head) /求表head的长度 _; j=0; while(p-next!=NULL) _; j+; return(j); /返回表长度 第8页/共125页 10/125 10以下为带头结点的单链表的定位运算，分析算法， 请在_处填上正确的语句。 int locate_lklist(lklist head,datatype x) /求表head中第一个值

6、等于x的结点的序号。不存在这种 结点时结果为0 p=head-next; j=0; while(_) p=p- next;j+; if (p-data=x) return(j); else return(0); 第9页/共125页 11/125 11循环链表与单链表的区别仅仅在于其终端结点的指 针域值不是_，而是一个指向_的指针。 第10页/共125页 12/125 三、选择题三、选择题 1线性结构中的一个结点代表一个( )。 A. 数据元素 B. 数据项 C. 数据 D. 数据结构 2对于顺序表，以下说法错误的是( )。 A. 顺序表是用一维数组实现的线性表，数组的下标可以 看成是元素的绝对

7、地址 B. 顺序表的所有存储结点按相应数据元素间的逻辑关系 决定的次序依次排列 C. 顺序表的特点是：逻辑结构中相邻的结点在存储结构 中仍相邻 D. 顺序表的特点是：逻辑上相邻的元素存储在物理位置 也相邻的单元中 第11页/共125页 13/125 3对顺序表上的插入、删除算法的时间复杂性分析来说， 通常以( )为标准操作。 A. 条件判断 B. 结点移动 C. 算术表达式 D. 赋值语句 4对于顺序表的优缺点，以下说法错误的是( )。 A. 无需为表示结点间的逻辑关系而增加额外的存储空间 B. 可以方便地随机存取表中的任一结点 C. 插入和删除运算较为方便 D. 容易造成一部分空间长期闲置而

8、得不到充分利用 第12页/共125页 14/125 5在循环链表中，将头指针改设为尾指针(rear)后，其头 结点和尾结点的存储位置分别是 ( )。 A. real和rear-next-next B. rear-next 和real C. rear-next-next和rear D. rear和rear-next 6设指针P指向双向链表的某一结点，则双向链表结构 的对称性可用( )来描述。 A. p-prior-next-=p-next-next B. p-prior-prior-=p-next-prior C. p-prior-next-=p-next-prior D. p-next-nex

9、t=p-prior-prior 第13页/共125页 15/125 7循环链表的主要优点是( )。 A. 不再需要头指针 B. 已知某个结点的位置后，能够容易找到它的直接前趋 C. 在进行插入、删除运算时，能更好地保证链表不断开 D. 从表中任一结点出发都能扫描到整个链表 第14页/共125页 16/125 8设rear是指向非空带头结点的循环单链表的尾指针，则 删除表首结点的操作可表示为( )。 A. p=rear; B. rear=rear-next; rear=rear-next; free(rear); free(p) C. rear=rear-next-next; D. p=rear

10、-next-next; free(rear); rear-next-next=p-next; free(p); 第15页/共125页 17/125 第16页/共125页 18/125 下面给出的算法段是要把一个新结点*q作为非空双向链 表中的结点*p的前驱，插入到此双向链表中。不能正确完成 要求的算法段是( )。 A. q-LLink=p-LLink; B. p-LLink=q; q-Rlink=p; q-Rlink=p; p-LLink=q; p-LLink-Rlink=q; p-LLink-Rlink=q; q-LLink=p-LLink; C. q-LLink=p-LLink; q-Rl

11、ink=p; p-LLink-Rlink=q; p-LLink=q; 第17页/共125页 19/125 10若某线性表中最常用的操作是取第i个元素和找第i个 元素的前趋元素，则采用( )存储方式最节省时间。 A. 顺序表 B. 单链表 C. 双链表 D. 单循环链表 第18页/共125页 20/125 四、算法设计四、算法设计 1设A=(a1,a2,a3,an)和B=(b1,b2, ,bm)是两个线性表(假 定所含数据元素均为整数)。若n=m且ai=bi(i=1, , n)，则称 A=B；若ai=bi(i=1, , j)且aj+1bj+1(jn=m)，则称AB。试编写一个比较A和B的算法，当

12、AB时，分别输出-1，0或1。 2分别以顺序表和单链表作存储结构，各写一个实现线 性表的就地(即使用尽可能少的附加空间)逆置的算法，在原表 的存储空间内将线性表(a1，a2, , an)逆置为(an, a2, a1)。 第19页/共125页 21/125 3已知单链表L中的结点是按值非递减有序排列的，试 写一算法，将值为x的结点插入表L中，使得L仍然有序。 4已知单链表L是一个递增有序表，试编写一高效算法， 删除表中值大于min且小于max的结点(若表中有这样的结点)， 同时释放被删除结点的空间，这里min和max是两个给定的参 数。请分析算法的时间复杂度。 5设A和B是两个单链表，表中元素递

13、增有序。试编写 一个算法，将A和B归并成一个按元素值递减有序的单链表C， 并要求辅助空间为O(1)，C表的头结点可另辟空间。请分析算 法的时间复杂度。 第20页/共125页 22/125 6已知一单链表中的数据元素含有三个字符(即字母字 符、数字字符和其它字符)。试编写算法，构造三个循环链表， 使每个循环链表中只含同一类的字符，且利用原表中的结点 空间作为这三个表的结点空间(头结点可另辟空间)。 7已知A、B和C为三个元素值递增有序的线性表，现要 求对表A作如下运算： 删去那些既在表B中出现又在表C中出 现的元素。试分别以两种存储结构(顺序结构和链式结构)编写 实现上述运算的算法。 8假设在长

14、度大于1的循环链表中，既无头结点也无头 指针，s为指向链表中某个结点的指针，试编写算法删除结点 *s的直接前趋结点。 第21页/共125页 23/125 栈和队列栈和队列 一、名词解释一、名词解释 栈，顺序栈，链栈，队列，顺序队列，循环列队，链队 二、填空题二、填空题 1栈修改的原则是_，因此，栈又称为 _线性表。在栈顶进行插入运算，被称为_， 在栈顶进行删除运算，被称为_。 2对于顺序栈而言，top=0表示_，此时作退栈 运算，则产生“_”；top=stack_maxsize-1表示 _，此时作进栈运算，则产生“_”。 第22页/共125页 24/125 3以下运算实现在顺序栈上的进栈，请在

15、_处用适 当的语句予以填充。 第23页/共125页 25/125 5以下运算实现循环队列的初始化，请在_处用 适当句子予以填充。 void InitCycQueue(Cycqueue* _; sq-rear=0; 6链队在一定范围内不会出现_的情况。 当lq-front=lq-rear时，称为_。 第24页/共125页 26/125 7以下运算实现在链队上取队头元素，请在_处 用适当句子予以填充。 int GetFront(LinkQ*lq,DataType *x) LinkQ *p; if(lq-rear=lq-front) return(0); else_; _ =p-data; retu

16、rn(1); 第25页/共125页 27/125 三、选择题三、选择题 1设有一顺序栈S，元素s1, s2, s3, s4, s5, s6依次进栈，如 果6个元素出栈的顺序是s2, s3, s4, s6, s5, s1，则栈的容量至少应 该是( )。 A. 2 B. 3 C. 5 D. 6 2一个栈的入栈序列是a, b, c, d, e, 则栈的不可能的输出 序列是( )。 A. e d c b a B. d e c b a C. d c e a b D. a b c d e 3一个栈的入栈序列是a, b, c, d, e, 则栈的不可能的输出 序列是( )。 A. e d c b a B.

17、d e c b a C. d c e a b D. a b c d e 第26页/共125页 28/125 第27页/共125页 29/125 5向一个栈顶指针为Top的链中插入一个s所指结点时， 其操作步骤为( )。 A. Top-next=s B. s-next=Top-next;Top-next=s C. s-next=Top;Top=s D. s-next=Top;Top=Top-next 6从栈顶指针为Top的链栈中删除一个结点，并将被删 节点的值保存到x中，其操作步骤为( )。 A. x=Top-data;Top=Top-next B. Top=Top-next;x=Top-dat

18、a C. x=Top;Top=Top-next D. x=Top-data 第28页/共125页 30/125 7循环队列的入队操作应为( )。 A. sq.rear=sq.rear+1;sq.datasq.rear=x; B. sq.datasq.rear=x;sq.rear=sq.rear+1; C. sq.rear=(sq.rear+1)%maxsize;sq.datasq.rear=x; D. sq.datasq.rear=x;sq.rear=(sq.rear+1)%maxsize; 8循环队列的队空条件为( )。 A. (sq.rear+1)%maxsize=(sq.front+1)

19、%maxsize B. (sq.rear+1)%maxsize=sq.front+1 C. (sp.rear+1)%maxsize=sq.front D. sq.rear=sq.front 第29页/共125页 31/125 四、算法设计四、算法设计 1回文是指从左向右读和从右向左读均相同的字符序列， 如“level”是回文，但“good”不是回文。试写一个算法判定 给定的字符向量是否为回文。(提示：将一半字符入栈，然后 出栈与另一半字符进行比较。) 2借助栈(可用栈的基本运算)来实现单链表的逆置运算。 3利用栈的基本运算将栈S中值为m的元素全部删除。 第30页/共125页 32/125 4假

20、设一个算术表达式中包含三种括号：圆括号“(”和 “)”，方括号“”和“”以及花括号“”和“”，且这三种括 号可按任意的次序嵌套使用，如(. . . . . . . . ( . . . .)。试利用栈的运算编写判断给定表达式中所含括 号是否正确配对出现的算法int correct(exp)；其中exp为字符串 类型的变量。如果括号正确配对，则返回值1；否则返回值0。 (提示：对表达式进行扫描，凡遇到“(”、“”或“”就入栈， 当遇到“)”、“”或“”时，检查当前栈顶元素是否是对应的 左括号，若是就退掉栈顶的“(”、“”或“”，否则不配对。 表达式扫描完毕，栈应为空。) 第31页/共125页 33

21、/125 5设函数 f(m,n)按下式定义( m,n 为大于 0 的整数)： )1n,m( f , 1m( f 1nm )n,m( f 时当 时当 0n*m 0n*m 试写出递归算法。 6假设以数组 cycquem(假设数组范围在 0.m -1)存放循 环队列的元素，同时设变量 rear 和 quelen 分别指示循环队列中队尾元素的位置和内含元素 的个数。试给出此循环队列的队满条件，并写出相应的入队列 和出队列的算法。 第32页/共125页 34/125 串和数组串和数组 一、名词解释一、名词解释 串，顺序串，链串 二、填空题二、填空题 1含零个字符的串称为_串，用_表示。其他 串称为_串。

22、任何串中所含_的个数称为该串的长 度。 2当且仅当两个串的_相等并且各个对应位置上的 字符都_时，这两个串相等。一个串中任意个连续字符 组成的序列称为该串的_串，该串称为它所有子串的 _串。 第33页/共125页 35/125 3通常将链串中每个存储结点所存储的字符个数称为 _。当结点大小大于1时，链串的最后一个结点的各个数 据域不一定总能全被字符占满，此时，应在这些未用的数据 域里补上_。 4一般地，一个n维数组可视为其数据元素为_维 数组的线性表。数组通常只有_和_两种基本运算。 5通常采用_存储结构来存放数组。对二维数组 可有两种存储方法：一种是以_为主序的存储方式，另 一种是以_为主序

23、的存储方式。C语言数组用的是以 _序为主序的存储方法。 第34页/共125页 36/125 6数组M中每个元素的长度是3个字节，行下标i从1到8， 列下标j从1到10，从首地址EA开始连续存放在存储器中。若 按行方式存放，则元素M85的起始地址为_；若按列 优先方式存放，则元素M85的地址为_。 7二维数组M的成员是6个字符(每个字符占一个存储单 元)组成的串，行下标i的范围从0到8，列下标j的范围从1到10， 则存放M至少需要_个字节；M的第8列和第5行共占 _个字节；若M按行方式存储，元素M85的起始地址 与当M按列优先方式存储时的_元素的起始地址一致。 第35页/共125页 37/125

24、 8需要压缩存储的矩阵可分为_矩阵和_矩 阵两种。 9对称方阵中有近半的元素重复，若为每一对元素只分 配一个存储空间，则可将n2个元素压缩存储到_个元素 的存储空间中。 10假设以一维数组M(1.n(n+1)/2)作为n阶对称矩阵A的 存储结构，以行序为主序存储其下三角(包括对角线)中的元素， 数组M和矩阵A间对应的关系为_。 第36页/共125页 38/125 11上三角矩阵中，主对角线上的第t行(1tn)有_ 个元素，按行优先顺序在一维数组M中存放上三角矩阵中的 元素aij时，aij之前的前i-1行共有_个元素，在第i行上， aij是该行的第_个元素，Mk和aij的对应关系是_。 当ij时

25、，aij=c(c表示常量)，c存放在M_中。 第37页/共125页 39/125 三、选择题三、选择题 1在串的基本运算中，能够改变串值的运算有( )。 A. EQAL(S,T) B. LENGTH(S) C. CONCAT(S,T) D. REPLACE(S,T,R) E. INDEX(S,T) 2在串的基本运算中，不能够改变串值的运算有( )。 A. ASSIGN(S,T) B. INSERT(S1,i,S2) C. DELETE(S,i,j)D. SUBSTR(S,i,j) E. REPLACE(S,T,R) 第38页/共125页 40/125 3对于以行序为主序的存储结构来说，在数组A

26、c1.d1， c2.d2中，c1和d1分别为数组A的第一个下标的下界和上界，c2 和d2分别为第二个下标的下界和上界，每个数据元素占K个存储 单元，二维数组中任一元素ai,j的存储位置可由( )式确定。 A. Loc(i,j)= Loc(c1, c2)+(i-c1)*(d2-c2) + (j-c2)*k B. Loc(i,j)=Loc(c1, c2)+(i-c1)*(d2-c2+1) + (j-c2)*k C. Loc(i,j)=Loc(c1, c2)+(j-c2)*(d1-c1+1) + (i-c1)*k D. Loc(i,j)= Loc(c1, c2)+(j-c2)*(d1-c1) + (

27、i-c1)*k 第39页/共125页 41/125 4对于C语言的二维数组DataType Amn,每个数据元素 占K个存储单元，二维数组中任意元素ai,j 的存储位置可由 ( )式确定。 A. Loc(i,j)=Loc(0,0)+ i*(n+1) +j*k B. Loc(i,j)=Loc(0,0)+ j*(m+1) +i*k C. Loc(i,j)=Loc(0,0)+(i*n +j)*k D. Loc(i,j)=Loc(0,0)+( j*m +i)*k 5稀疏矩阵的压缩存储方法是只存储( )。 A. 非零元素 B. 三元组(i,j, aij) C. aij D. i, j 第40页/共125

28、页 42/125 6基于三元组表的稀疏矩阵，对每个非零元素aij,可以用 一个( )唯一确定。 A. 非零元素 B. 三元组(i,j,aij) C. aij D. i,j 7二维数组Mi,j的元素是4个字符(每个字符占一个存储 单元)组成的串，行下标i的范围从0到4，列下标j的范围从0到 5。若M按行存储，元素M3,5的起始地址与M按列存储时， 元素( )的起始地址相同。 A. M 2,4 B. M3,4 C. M3,5 D. M4,4 8常对数组进行的两种基本操作是( )。 A. 建立与删除 B. 建立与修改 C. 查找与修改 D. 查找与索引 第41页/共125页 43/125 四、问答及

29、算法设计四、问答及算法设计 1简述下列各对术语的区别。 空串和空格串；串变量和串常量；主串和子串；串变量的 名字与串变量的值 第42页/共125页 44/125 2设有A=“ ”, B=“mule”，C=“old”，D=“my”,试计算下 列运算的结果(注：A+B是CONCAT(A,B)的简写, A=“ ”表示 含有两个空格的字符串)。 (a) A+B (b) B+A (c) D+C+B (d) SUBSTR(B,3,2) (e) SUBSTR(C,1,0) (f) LENGTH(A) (g) LENGTH(D) (h) INDEX(B,D) (i) INDEX(C,“d”)(j) INSER

30、T(D,2,C) (k) INSERT(B,1,A) (l) DELETE(B,2,2) (m) DELETE(B,2,0) 第43页/共125页 45/125 3分别在顺序串和链串上实现串的判相等运算 EQUAL(S,T)。 4若S和T是用结点大小为1的单链表存储的两个串(S、T 为头指针)，设计一个算法将串S中首次与串T匹配的子串逆置。 5用串的其他运算构造串的子串定位运算index。 6利用C的库函数strlen、strcpy和strcat写一算法void StrInsert(char*S,char*T)，将串T插入到串S的第i个位置上。若i 大于S的长度，则插入不执行。 第44页/共1

31、25页 46/125 7利用C的库函数strlen、strcpy和strncpy写一算法void StrDelete(char*S,int i,int m)，删去串S中从位置i开始的连续m 个字符。若istrlen(S)，则没有字符被删除；若i+mstrlen(S)， 则将S中从位置i开始直至末尾的字符均删去。 8设有三对角矩阵Ann，将其三条对角线上的元素逐行 存于数组A(1.3n-2)中，使得Ak=aij。求： (1) 用i、j表示k的下标变换公式； (2) 用k表示i、j的下标变换公式。 第45页/共125页 47/125 树和二叉树树和二叉树 一、名词解释一、名词解释 树，结点的度，叶

32、子，树的度，父结点，子结点，兄弟， 结点的层数，树的高度，二叉树，左孩子，右孩子，满二叉 树，完全二叉树 二、填空题二、填空题 1假定在一棵二叉树中，双分支结点数为15个，单分支 结点数为32个，则叶子结点数为 。 2假定一棵二叉树的结点数为18个，则它的最小高度 是 ，最大高度是 。 第46页/共125页 48/125 3在一棵二叉树中第4层上的结点数最多为 。 4如果结点A有三个兄弟，而且B是A的双亲，则B的出 度是 。 5在完全二叉树中，当i为奇数且不等于时，结点i的 左兄弟是结点 ，否则没有左兄弟。 6对于一棵具有n个结点的树，该树中所有结点的度之 和为 。 7在二叉树的顺序存储中，对

33、于下标为5的结点，它的 双亲结点的下标为 ；若它存在左孩子，则左孩子结点的下 标为 ；若它存在右孩子，则右孩子结点的下标为 。 8在一棵二叉排序树中，按 遍历得到的结点序列是 一个有序序列。 第47页/共125页 49/125 三、选择题三、选择题 1以下说法错误的是( )。 A. 树形结构的特点是一个结点可以有多个直接前趋 B. 树形结构可以表达(组织)更复杂的数据 C. 树(及一切树形结构)是一种“分支层次”结构 D. 任何只含一个结点的集合是一棵树 2深度为6的二叉树最多有( )个结点。 A. 64 B. 63 C. 32 D. 31 3任何一棵二叉树的叶结点在其先序、中序、后序遍历 序

34、列中的相对位置( )。 A. 肯定发生变化 B. 有时发生变化 C. 肯定不发生变化 D. 无法确定 第48页/共125页 50/125 4设深度为k的二叉树上只有度为0和度为2的结点，则这 类二叉树上所含结点总数最少为( )个。 A. k+1 B. 2k C. 2k-1 D.2k+1 5一棵二叉树满足下列条件：对于任意结点，其值都大 于它的左子树上所有结点的值，而小于右子树上所有结点的 值。现采用( )遍历方式就可以得到这棵二叉树所有结点的递 增序列。 A. 先序 B. 中序 C. 后序 D. 层次 6已知某二叉树的后序遍历序列是dabec，中序遍历序 列是deabc，它的先序遍历序列是(

35、)。 A. acbed B. deabc C. decab D. cedba 第49页/共125页 51/125 四、简答及算法设计四、简答及算法设计 1画出由3个结点所构成的所有形态的树(假设是无序树)。 2一棵深度为H的满k叉树有如下性质：第H层上的结点 都是叶子结点，其余各层上每个结点都有k棵非空子树。如果 按层次自顶向下，同一层自左向右从1开始对全部结点进行编 号，试问： (1) 各层的结点个数是多少？ (2) 编号为i的结点的双亲结点(若存在)的编号是多少？ (3) 编号为i的结点的第m个孩子结点(若存在)的编号是多少? (4) 编号为i的结点有右兄弟的条件是什么？右兄弟结点的 编号

36、是多少？ 第50页/共125页 52/125 3分别描述满足下面条件的二叉树的特征： (1) 先序序列和中序序列相同。 (2) 先序序列和后序序列相同。 (3) 中序序列和后序序列相同。 4已知某二叉树的先序遍历序列为ABC，试画出能得到 这一结果的所有二叉树。 5已知二叉树的后序序列DECBGIHFA和中序序列 DCEBAFHGI，画出这棵二叉树。 6分别设计出先序和后序遍历二叉树的非递归算法。 第51页/共125页 53/125 7已知二叉树采用二叉链表存储结构，编写一个算法， 交换二叉树所有左、右子树的位置，即结点的左子树变为结 点的右子树，右子树变为左子树。 8采用二叉链表结构存储一棵

37、二叉树，编写一个算法， 删除该二叉树中数据值为x的结点及其子树，并且输出被删除 的子树。 9试以三种遍历为基础，分别写出在二叉树上查找指定 结点的直接前趋或直接后继的算法。 10已知树(森林)的高度为4，所对应的二叉树的先序序 列为ABCDE，请构造出所有满足这一条件的树或森林。 软件技术基础电子教案 第52页/共125页 54/125 11将深度为4的满二叉树转换为对应的树或森林。 12已知结点序列21，18，37，42，65，24，19，26， 45，25，画出相应的二叉排序树，并画出删除结点37后的二 叉排序树。 13试编写一个判别给定二叉树是否为二叉排序树的算 法，设此二叉树以二叉链表

38、作存储结构。 软件技术基础电子教案 第53页/共125页 55/125 图图 一、名词解释一、名词解释 图，无向完全图，有向完全图，子图，连通分量，图的 遍历，拓扑排序 二、填空题二、填空题 1一个具有n个顶点的完全无向图的边数为 。一个 具有n个顶点的完全有向图的弧度数为 。 2设x,yV，若E, 则表示有向图G中从x到 y的一条 ，x称为 点，y称为 点。若(x,y)E，则在无 向图G中x和y间有一条 。 第54页/共125页 56/125 3在无向图中，如果从顶点v到顶点v有路径，则称v和 v是 的。如果对于图中的任意两个顶点vi,vjV，且vi和vj 都是连通的，则称G为 。 4连通分

39、量是无向图中的 连通子图。 5若连通图G的顶点个数为n，则G的生成树的边数 为 。如果G的一个子图G的边数_，则G中一定 有环。相反，如果G的边数 ，则G一定不连通。 6对于无向图的邻接矩阵，顶点vi的度是 。对于有 向图的邻接矩阵，顶点vi的出度OD(vi)为 ，顶点vi的入度 ID(vi)为 。 软件技术基础电子教案 第55页/共125页 57/125 7图的深度优先搜索遍历类似于树的 遍历，它所用 到的数据结构是 ；图的广度优先搜索遍历类似于树的 遍历，它所用到的数据结构是 。 8一个图的 表示法是唯一的，而 表示法是不唯 一的。 9在有向图的邻接矩阵上，由第i行可得到第 个结点 的出度

40、，而由第j列可得到第 个结点的入度。 10在无向图中，所有顶点的度数之和是所有边数的 倍，在有向图中，所有顶点的入度之和是所有顶点出度之 和的 倍。 软件技术基础电子教案 第56页/共125页 58/125 11以下是图的深度优先算法，请在 处填充适当的语句。 void DFS(GraphTp g,int v) ArcNodeTp *p; printf(%d,v); visitedv=1; p= ; while(p!=NULL) if(! ) DFS(g,p-adjvex); p= ; 软件技术基础电子教案 第57页/共125页 59/125 三、选择题三、选择题 1在无向图中，所有顶点的度数

41、之和是所有边数的( ) 倍。 A. 0.5 B. 1 C. 2 D. 4 2在有向图中，所有顶点的入度之和是所有顶点出度之 和的( )倍。 A. 0.5 B. 1 C. 2 D. 4 3设有6个结点的无向图，该图至少应有( )条边能确保 是一个连通图。 A. 5 B. 6 C. 7 D. 8 第58页/共125页 60/125 4以下说法中错误的是( )。 A. 用相邻矩阵法存储一个图时，在不考虑压缩存储的情 况下，所占用的存储空间的大小只与图中结点个数有关，而 与图的边数无关 B. 邻接表法只能用于有向图的存储，而相邻矩阵法对于 有向图和无向图的存储都适用 C. 存储无向图的相邻矩阵是对称的

42、，因此只要存储相邻 矩阵的下(或上)三角部分就可以了 D. 用相邻矩阵A表示图，判定任意两个结点vi和vj之间是 否有长度为m的路径相连，则只要检查A的第 i行第j列的元素 是否为0即可 软件技术基础电子教案 第59页/共125页 61/125 四、简答及算法设计四、简答及算法设计 1写出将一个无向图的邻接矩阵转换成邻接表的算法。 2写出将一个无向图的邻接表转换成邻接矩阵的算法。 3写出建立一个有向图的逆邻接表的算法。 4给定的无向图如图3.1所示，写出其邻接表，并以顶点 1为出发点，写出其深度优先搜索和广度优先搜索所经过的顶 点和边序列。 第60页/共125页 62/125 图3.1 软件技

43、术基础电子教案 第61页/共125页 63/125 5设有一无向图G=(V, E)，其中V=1,2,3,4,5,6,E= (1,2),(1,6),(2,6),(1,4),(6,4),(1,3),(3,4),(6,5),(4,5),(1,5),(3,5)，按 上述顺序输入后，画出其相应的邻接表。 6在该邻接表上，从顶点4开始，写出DFS序列和BFS序 列。 7已给有向图如图3.2所示，利用Dijkstra算法求v0到各顶 点的最短路径，并写出算法执行时每次循环的状态。 软件技术基础电子教案 第62页/共125页 64/125 图3.2 软件技术基础电子教案 第63页/共125页 65/125 8

44、对图3.3所示AOE网，求出： (1) 各活动的最早开始时间和最迟开始时间； (2) 所有的关键路径； (3) 完成该网络所代表的工程工期； (4) 提高哪些关键活动的速度可缩短工期？ 第64页/共125页 66/125 图3.3 软件技术基础电子教案 第65页/共125页 67/125 查找查找 一、名词解释一、名词解释 查找表，查找长度，有序表，散列表，散列函数，同义 词，冲突 二、填空题二、填空题 1查找表中主关键字指的是 ，次关键字指的是 。 2二分查找在查找成功时的查找长度不超过 ，其平 均查找长度为 ，当n较大时约等于 。 3在散列存储中，装填因子的值越大，则 。 第66页/共12

45、5页 68/125 4二分查找法仅适用于这样的表：表中的记录必须 ， 其存储结构必须是 。 5静态查找表的三种不同实现各有优缺点。其中， 查找效率最低但限制最少， 查找效率最高但限制最强， 而 查找则介于上述二者之间。 6设有一个已按各元素的值排好序的线性表，长度为 125，对给定的k值，用二分法查找与k相等的元素，若查找成 功，则至少需比较 次，至多需比较 次。 7在采用开放地址法解决冲突的散列表中删除一个记录， 则对该元素所在存储单元的操作是 。 软件技术基础电子教案 第67页/共125页 69/125 8以下算法在散列表HP中查找键值等于K的结点，成功 时返回指向该结点的指针，不成功时返

46、回空指针。请分析程 序，并在 上填充合适的语句。 pointer research_openhash(keytype K,openhash HP) i=H(K); / 计算K的散列地址 p=HPi; / i的同义词子表表头指针传给p while( )p=p-next; / 未达表尾且未找到时，继 续扫描 _; 软件技术基础电子教案 第68页/共125页 70/125 9以下算法假定以线性探测法解决冲突，在散列表HL 中查找键值为K的结点，成功时回送该位置，不成功时回送标 志-1。请分析程序，并在 上填充合适的语句。 int search_cloxehash(keytype K,closehas

47、h HL) d=H(K); / 计算散列地址 i=d; while(HLi.key!=K /未成功且未查 遍整个HL时继续扫描 if( )reurn(i); /查找成功 else return(-1); /查找失败 软件技术基础电子教案 第69页/共125页 71/125 三、选择题三、选择题 1顺序查找法适合于( )存储结构的查找表。 A. 压缩 B. 散列 C. 索引 D. 顺序或链式 2对采用折半查找法进行查找运算的查找表，要求按 ( )方式进行存储。 A. 顺序存储 B. 链式存储 C. 顺序存储且结点按关键字有序 D. 链式存储且结点按关键字有序 第70页/共125页 72/125

48、3设顺序表的长为n，则其每个元素的平均查找长度是 ( )。 A. n B. (n-1)/2 C. n/2 D. (n+1)/2 4分块查找的时间性能( )。 A. 低于二分查找 B. 高于顺序查找而低于二分查 找 C. 高于顺序查找 D. 低于顺序查找而高于二分查 找 5设有序表的关键字序列为1，4，6，10，18，35，42， 53，67，71，78，84，92，99，当用折半查找法查找键值为84 的结点时，经( )次比较后查找成功。 A. 2 B. 3 C. 4 D. 12 第71页/共125页 73/125 6用二分查找法对具有n个结点的线性表查找的时间复 杂性量级为( )。 A. O(

49、n2) B. O(nlbn) C. O(n) D. O(lbn) 7与其他查找方法相比，散列查找法的特点是( )。 A. 通过关键字比较进行查找 B. 通过关键字计算记录存储地址进行查找 C. 通过关键字比较或通过关键字计算记录存储地址进行 查找 D. 通过关键字计算记录存储地址，并进行一定的比较进 行查找 软件技术基础电子教案 第72页/共125页 74/125 8在采用线性探测法处理冲突所构成的闭散列表上进行 查找，可能要探测多个位置，在查找成功的情况下，所探测 的这些位置上的键值( )。 A. 一定都是同义词 B. 一定都不是同义词 C. 都相同 D. 不一定是有序的顺序表 软件技术基础

50、电子教案 第73页/共125页 75/125 9以下说法中错误的是( )。 A. 散列法存储的基本思想是由关键码的值决定数据的存 储地址 B. 散列表的结点中只包含数据元素自身的信息，不包含 任何指针 C. 装填因子是散列法的一个重要参数，它反映散列表的 装填程度 D. 散列表的查找效率主要取决于散列表造表时选取的散 列函数和处理冲突的方法 软件技术基础电子教案 第74页/共125页 76/125 四、简答及算法设计四、简答及算法设计 1假设线性表中结点是按键值递增的顺序存放的。试写 一顺序查找法，将岗哨设在高下标端，然后分别求出等概率 情况下查找成功和不成功时的平均查找长度。 2若线性表中各

51、结点的查找概率不等，则可用如下策略 提高顺序查找的效率：若找到指定的结点，则将该结点和其 前趋(若存在)结点交换，使得经常被查找的结点尽量位于表的 前端。试对线性表的顺序存储结构和链式存储结构写出实现 上述策略的顺序查找算法(注意，查找时必须从表头开始向后 扫描)。 3试写出折半查找的递归算法。 软件技术基础电子教案 第75页/共125页 77/125 4给定有序表： D=006,087,155,188,220,465,505,508,511,586,656,670, 700,766,897,908 用折半查找法在D中查找586，试用图示法表示出查找过程。 5已知散列函数为H(K)=K mod

52、 13，关键字序列为25， 37，52，43，84，99，120，15，26，11，70，82，试分别画 出采用线性探查法和拉链法处理冲突时的散列表，并计算查 找成功的平均查找长度。 6顺序查找时间为O(n),二分查找时间为O(lbn),散列查找 时间为O(1)，为什么在已有高效率的查找方法时仍不放弃低 效率的方法？ 软件技术基础电子教案 第76页/共125页 78/125 查找查找 一、名词解释一、名词解释 排序，稳定的排序，不稳定的排序，内部排序，外部排 序 二、填空题二、填空题 1按照排序过程涉及的存储设备的不同，排序可分为 排序和 排序。 2在排序算法中，分析算法的时间复杂性时，通常以

53、 和 为标准操作。评价排序的另一个主要标准是执行算法所 需要的 。 3直接插入排序是稳定的，它的时间复杂性为 ，空 间复杂度为 。 软件技术基础电子教案 第77页/共125页 79/125 4对于n个记录的集合进行起泡排序，其最坏情况下所 需的时间复杂度为 。 5对于n个记录的集合进行归并排序，所需的附加空间 消耗是 。 6以下为起泡排序的算法。请分析算法，并在 上填 充适当的语句。 软件技术基础电子教案 第78页/共125页 80/125 7对快速排序来讲，其最好情况下的时间复杂度是 ， 其最坏情况下的时间复杂度是 。 8归并排序要求待排序列由若干个 的子序列组成。 三、选择题三、选择题 1

54、以下不稳定的排序方法是( )。 A. 直接插入排序 B. 起泡排序 D. 直接选择排序 D. 二路归并排序 第79页/共125页 81/125 2以下时间复杂性不是O(n2)的排序方法是( )。 A. 直接插入排序 B. 二路归并排序 C. 起泡排序 D. 直接选择排序 3排序的目的是为了以后对已排序的数据元数进行( ) 操作。 A. 打印输出 B. 分类 C. 合并 D. 查找 4具有24个记录的序列，采用起泡排序至少的比较次数 是( )。 A. 1 B. 23 C. 24 D. 529 软件技术基础电子教案 第80页/共125页 82/125 5用某种排序方法对序列(25，84，21，47

55、，15，27，68， 35，20)进行排序，记录序列的变化情况如下： 25 84 21 47 15 27 68 35 20 15 20 21 25 47 27 68 35 84 15 20 21 25 35 27 47 68 84 15 20 21 25 27 35 47 68 84 则采取的排序方法是( )。 A. 直接选择排序 B. 起泡排序 C. 快速排序 D. 二路归并排序 软件技术基础电子教案 第81页/共125页 83/125 6( )方法是从未排序序列中依次取出元素与已排序序 列中的元素作比较，将其放入已排序序列的正确位置上。 A. 归并排序 B. 插入排序 C. 快速排序 D.

56、 选择排序 7( )方法是对序列中的元素通过适当的位置交换，将 有关元素一次性地放置在其最终位置上。 A. 归并排序 B. 插入排序 C. 快速排序 D. 选择排序 8将上万个一组无序并且互不相等的正整数序列，存放 于顺序存储结构中，采用( )方法能够最快地找出其中最大的 正整数。 A. 快速排序 B. 插入排序 C. 选择排序 D. 归 并排序 软件技术基础电子教案 第82页/共125页 84/125 四、简答及算法设计四、简答及算法设计 1给定关键字序列：105，50，30，25，85，40，100， 12，10，28，分别写出直接插入排序、希尔排序、起泡排序、 直接选择排序、快速排序和归

57、并排序的每一趟运行结果。 2试给出上题中直接插入排序、希尔排序、起泡排序、 直接选择排序、快速排序和归并排序在最好和最坏时的关键 字序列，指出比较和移动次数，以及相应的时间复杂度。 3举例说明本章介绍的各排序方法中哪些是不稳定的。 第83页/共125页 85/125 4已知数组An中的元素为整型，设计算法将其中所有 的奇数调整到数组的左边，而将所有的偶数调整到数组的右 边，并要求时间复杂度为O(n)。 5试在单链表上实现起泡排序。 6试在单链表上实现直接插入排序。 7试在单链表上实现直接选择排序。 8一个线性表中的元素为正整数或负整数。设计一个算 法，将正整数和负整数分开，使线性表前一半为负整

58、数，后 一半为正整数。不要求对这些元素排序，但要求尽量减少交 换次数。 软件技术基础电子教案 第84页/共125页 86/125 9设计算法以实现以下功能：不用完整排序，找出按增 序关系为第k位的元素。 10设计算法以实现以下功能：不用完整排序，要求找 出其中最大的10个数，并回答选用何种排序算法最节省时间？ 11试写出递归形式的归并排序算法。 12采用希尔排序方法对顺序表中的整型数据进行排序， 设计希尔排序算法并显示每趟排序的结果。 13编写一个双向起泡的排序算法，即在排序过程中交 替改变扫描方向，同时显示各趟排序的结果。 软件技术基础电子教案 第85页/共125页 87/125 14下面是

59、一个自下往上扫描的改进的起泡排序算法， 按照给定的关键字序列：49，31，63，85，75，15，26，49。 试分析共排序了几趟，并写出各趟排序的结果。 void BubbleSort(rectype R , int n) int i=1, j, k; while(ii; j-) if(Rj-1.keyRj.key) swap(Rj-1,Rj); k=j; i=k; /将 i 置为最后交换的位置 软件技术基础电子教案 第86页/共125页 88/125 软件技术基础电子教案 第87页/共125页 89/125 l操作系统概述操作系统概述 一、选择题一、选择题 1操作系统是一种系统软件，它的职

60、能是()。 A. 只管理软件B. 只管理硬件 C. 既不管理硬件，也不管理软件 D. 既管理硬件，也管理软件 2设计批处理操作系统时，首先应考虑的是()。 A. 交互性和响应时间B. 吞吐量和周转时间 C. 灵活性和可适应性D. 可靠性和完整性 软件技术基础电子教案 第88页/共125页 90/125 3设计分时操作系统的主要目标是( )。 A吞吐量和周转时间B交互性和响应时间 C灵活性和可适应性D可靠性和完整性 4对计算机系统起着控制和管理作用的是( )。 A硬件 B操作系统 C编译系统 D应用程序 5在( )操作系统的控制下，计算机能及时处理过程控 制装置反馈的信息，并作出响应。 A网络