第1章 绪论
1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。
解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。
数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。
数据类型是一个值的集合和定义在这个值集上的一组操作的总称。
抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。
解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中
{}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r =
试按图论中图的画法惯例画出其逻辑结构图。
解：
1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解：
ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={
操作结果：构造一个复数C ，其实部和虚部分别为re 和im DestroyCmoplex(&C)
操作结果：销毁复数C Get(C,k,&e) 操作结果：用e 返回复数C 的第k 元的值 Put(&C,k,e) 操作结果：改变复数C 的第k 元的值为e
IsAscending(C)
操作结果：如果复数C 的两个元素按升序排列，则返回1，否则返回0
IsDescending(C)
操作结果：如果复数C的两个元素按降序排列，则返回1，否则返回0 Max(C,&e)
操作结果：用e返回复数C的两个元素中值较大的一个
Min(C,&e)
操作结果：用e返回复数C的两个元素中值较小的一个}ADT Complex
ADT RationalNumber{
数据对象：D={s,m|s,m为自然数，且m不为0}
数据关系：R={
基本操作：
InitRationalNumber(&R,s,m)
操作结果：构造一个有理数R，其分子和分母分别为s和m
DestroyRationalNumber(&R)
操作结果：销毁有理数R
Get(R,k,&e)
操作结果：用e返回有理数R的第k元的值
Put(&R,k,e)
操作结果：改变有理数R的第k元的值为e
IsAscending(R)
操作结果：若有理数R的两个元素按升序排列，则返回1，否则返回0 IsDescending(R)
操作结果：若有理数R的两个元素按降序排列，则返回1，否则返回0 Max(R,&e)
操作结果：用e返回有理数R的两个元素中值较大的一个
Min(R,&e)
操作结果：用e返回有理数R的两个元素中值较小的一个}ADT RationalNumber
1.5 试画出与下列程序段等价的框图。
(1) product=1; i=1;
while(i<=n){
product *= i;
i++;
}
(2) i=0;
do {
i++;
} while((i!=n) && (a[i]!=x));
(3) switch {
case x case x=y: z=abs(x*y); break; default: z=(x-y)/abs(x)*abs(y); } 1.6 在程序设计中，常用下列三种不同的出错处理方式： (1) 用exit语句终止执行并报告错误； (2) 以函数的返回值区别正确返回或错误返回； (3) 设置一个整型变量的函数参数以区别正确返回或某种错误返回。 试讨论这三种方法各自的优缺点。 解：(1)exit常用于异常错误处理，它可以强行中断程序的执行，返回操作系统。 (2)以函数的返回值判断正确与否常用于子程序的测试，便于实现程序的局部控制。 (3)用整型函数进行错误处理的优点是可以给出错误类型，便于迅速确定错误。 1.7 在程序设计中，可采用下列三种方法实现输出和输入： (1) 通过scanf和printf语句； (2) 通过函数的参数显式传递； (3) 通过全局变量隐式传递。 试讨论这三种方法的优缺点。 解：(1)用scanf和printf直接进行输入输出的好处是形象、直观，但缺点是需要对其进行格式控制，较为烦琐，如果出现错误，则会引起整个系统的崩溃。 (2)通过函数的参数传递进行输入输出，便于实现信息的隐蔽，减少出错的可能。 (3)通过全局变量的隐式传递进行输入输出最为方便，只需修改变量的值即可，但过多的全局变量使程序的维护较为困难。 1.8 设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; while (i<=n-1) { i++; @ k += 10*i; } (4) k=0; for(i=1; i<=n; i++) { for(j=i; j<=n; j++) @ k++; } (5) for(i=1; i<=n; i++) { for(j=1; j<=i; j++) { for(k=1; k<=j; k++) @ x += delta; } (6) i=1; j=0; while(i+j<=n) { @ if(i>j) j++; else i++; } (7) x=n; y=0; // n 是不小于1的常数 while(x>=(y+1)*(y+1)) { @ y++; } (8) x=91; y=100; while(y>0) { @ if(x>100) { x -= 10; y--; } else x++; } 解：(1) n-1 (2) n-1 (3) n-1 (4) n+(n-1)+(n-2)+ (1) 2 ) 1(+n n (5) 1+(1+2)+(1+2+3)+...+(1+2+3+...+n)= ∑=+n i i i 1 2) 1( =∑∑∑∑====+=+=+n i n i n i n i i i i i i i 1 121212121)(21)1(21 = )32)(1(12 1 )1(41)12)(1(121++=++++n n n n n n n n (6) n (7) ??n 向下取整 (8) 1100 1.9 假设n 为2的乘幂，并且n>2，试求下列算法的时间复杂度及变量count 的值（以n 的函数形式表示）。 int Time(int n) { count = 0; x=2; while(x x *= 2; count++; } return count; } 解：)(log 2n o count=2log 2 -n 1.11 已知有实现同一功能的两个算法，其时间复杂度分别为()n O 2和()10 n O ，假设现实计算机可连续 运算的时间为710秒（100多天），又每秒可执行基本操作（根据这些操作来估算算法时间复杂度）5 10次。试问在此条件下，这两个算法可解问题的规模（即n 值的范围）各为多少？哪个算法更适宜？请说明理由。 解：12102 =n n=40 1210 10=n n=16 则对于同样的循环次数n ，在这个规模下，第二种算法所花费的代价要大得多。故在这个规模下，第一种算法更适宜。 1.12 设有以下三个函数： ()10002124++=n n n f ，()3450015n n n g +=，()n n n n h log 5005.3+= 请判断以下断言正确与否： (1) f(n)是O(g(n)) (2) h(n)是O(f(n)) (3) g(n)是O(h(n)) (4) h(n)是O(n 3.5 ) (5) h(n)是O(nlogn) 解：(1)对 (2)错 (3)错 (4)对 (5)错 1.13 试设定若干n 值，比较两函数2 n 和n n 2log 50的增长趋势，并确定n 在什么范围内，函数2n 的值 大于n n 2 log 50的值。 解：2 n 的增长趋势快。但在n 较小的时候，n n 2log 50的值较大。 当n>438时，n n n 22 log 50> 1.14 判断下列各对函数 ()n f 和()n g ，当∞→n 时，哪个函数增长更快？ (1) ()( )3 10!ln 102n n n n f ++=，()724 ++=n n n g (2) ()()() 2 5!ln +=n n f ，()5.213n n g = (3) ()141.2++=n n n f ，()()()n n n g +=2 !ln (4) ()()()2 223n n n f +=，()()52n n n g n += 解：(1)g(n)快 (2)g(n)快 (3)f(n)快 (4) f(n)快 1.15 试用数学归纳法证明： (1) ()()6/12112 ++=∑=n n n i n i ()0≥n (2) () ()1/11 --=+=∑x x x n n i i ()0,1≥≠n x (3) 122 11 -=∑=-n n i i ()1≥n (4) ()2 1 12n i n i =-∑= ()1≥n 1.16 试写一算法，自大至小依次输出顺序读入的三个整数X ，Y 和Z 的值 解： int max3(int x,int y,int z) { if(x>y) if(x>z) return x; else return z; else if(y>z) return y; else return z; } 1.17 已知k 阶斐波那契序列的定义为 00=f ，01=f ，…，02=-k f ，11=-k f ； k n n n n f f f f ---+++= 21， ,1,+=k k n 试编写求k 阶斐波那契序列的第m 项值的函数算法，k 和m 均以值调用的形式在函数参数表中出现。 解：k>0为阶数，n 为数列的第n 项 int Fibonacci(int k,int n) { if(k<1) exit(OVERFLOW); int *p,x; p=new int[k+1]; if(!p) exit(OVERFLOW); int i,j; for(i=0;i } for(i=k+1;i for(j=0;j return p[k]; } 1.18 假设有A ，B ，C ，D ，E 五个高等院校进行田径对抗赛，各院校的单项成绩均已存入计算机，并构成一张表，表中每一行的形式为 项目名称 性别 校名 成绩 得分 编写算法，处理上述表格，以统计各院校的男、女总分和团体总分，并输出。 解： typedef enum{A,B,C,D,E} SchoolName; typedef enum{Female,Male} SexType; typedef struct{ char event[3]; //项目 SexType sex; SchoolName school; int score; } Component; typedef struct{ int MaleSum; //男团总分 int FemaleSum; //女团总分 int TotalSum; //团体总分 } Sum; Sum SumScore(SchoolName sn,Component a[],int n) { Sum temp; temp.MaleSum=0; temp.FemaleSum=0; temp.TotalSum=0; int i; for(i=0;i } } temp.TotalSum=temp.MaleSum+temp.FemaleSum; return temp; } 1.19 试编写算法，计算i i 2!*的值并存入数组a[0..arrsize-1]的第i-1个分量中(i=1,2,…,n)。假设计算机中允许的整数最大值为maxint ，则当n>arrsize 或对某个()n k k ≤≤1，使int max 2!>?k k 时， 应按出错处理。注意选择你认为较好的出错处理方法。 解： #include int main() { int i,k; int a[ArrSize]; cout<<"Enter k:"; cin>>k; if(k>ArrSize-1) exit(0); for(i=0;i<=k;i++){ if(i==0) a[i]=1; else{ if(2*i*a[i-1]>MAXINT) exit(0); else a[i]=2*i*a[i-1]; } } for(i=0;i<=k;i++){ if(a[i]>MAXINT) exit(0); else cout< return 0; } 1.20 试编写算法求一元多项式的值()∑==n i i i n x a x P 0 的值()0x P n ，并确定算法中每一语句的执行次数 和整个算法的时间复杂度。注意选择你认为较好的输入和输出方法。本题的输入为()n i a i ,,1,0 =，0 x 和n ，输出为()0x P n 。 解： #include double polynomail(int a[],int i,double x,int n); int main() { double x; int n,i; int a[N]; cout<<"输入变量的值x:"; cin>>x; cout<<"输入多项式的阶次n:"; cin>>n; if(n>N-1) exit(0); cout<<"输入多项式的系数a[0]--a[n]:"; for(i=0;i<=n;i++) cin>>a[i]; cout<<"The polynomail value is "< return 0; } double polynomail(int a[],int i,double x,int n) { if(i>0) return a[n-i]+polynomail(a,i-1,x,n)*x; else return a[n]; } 本算法的时间复杂度为o(n)。 第2章线性表 2.1 描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。 解：头指针是指向链表中第一个结点的指针。首元结点是指链表中存储第一个数据元素的结点。头结点是在首元结点之前附设的一个结点，该结点不存储数据元素，其指针域指向首元结点，其作用主要是为了方便对链表的操作。它可以对空表、非空表以及首元结点的操作进行统一处理。 2.2 填空题。 解：(1) 在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与元素在表中的位置有关。 (2) 顺序表中逻辑上相邻的元素的物理位置必定紧邻。单链表中逻辑上相邻的元素的物理位置不一定紧邻。 (3) 在单链表中，除了首元结点外，任一结点的存储位置由其前驱结点的链域的值指示。 (4) 在单链表中设置头结点的作用是插入和删除首元结点时不用进行特殊处理。 2.3 在什么情况下用顺序表比链表好？ 解：当线性表的数据元素在物理位置上是连续存储的时候，用顺序表比用链表好，其特点是可以进行随机存取。 2.4 对以下单链表分别执行下列各程序段，并画出结果示意图。 解： 2.5 画出执行下列各行语句后各指针及链表的示意图。 L=(LinkList)malloc(sizeof(LNode)); P=L; for(i=1;i<=4;i++){ P->next=(LinkList)malloc(sizeof(LNode)); P=P->next; P->data=i*2-1; } P->next=NULL; for(i=4;i>=1;i--) Ins_LinkList(L,i+1,i*2); for(i=1;i<=3;i++) Del_LinkList(L,i); 解： 2.6 已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。 a. 在P结点后插入S结点的语句序列是__________________。 b. 在P结点前插入S结点的语句序列是__________________。 c. 在表首插入S结点的语句序列是__________________。 d. 在表尾插入S结点的语句序列是__________________。 (1) P->next=S; (2) P->next=P->next->next; (3) P->next=S->next; (4) S->next=P->next; (5) S->next=L; (6) S->next=NULL; (7) Q=P; (8) while(P->next!=Q) P=P->next; (9) while(P->next!=NULL) P=P->next; (10) P=Q; (11) P=L; (12) L=S; (13) L=P; 解：a. (4) (1) b. (7) (11) (8) (4) (1) c. (5) (12) d. (9) (1) (6) 2.7 已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。 a. 删除P结点的直接后继结点的语句序列是____________________。 b. 删除P结点的直接前驱结点的语句序列是____________________。 c. 删除P结点的语句序列是____________________。 d. 删除首元结点的语句序列是____________________。 e. 删除尾元结点的语句序列是____________________。 (1) P=P->next; (2) P->next=P; (3) P->next=P->next->next; (4) P=P->next->next; (5) while(P!=NULL) P=P->next; (6) while(Q->next!=NULL) { P=Q; Q=Q->next; } (7) while(P->next!=Q) P=P->next; (8) while(P->next->next!=Q) P=P->next; (9) while(P->next->next!=NULL) P=P->next; (10) Q=P; (11) Q=P->next; (12) P=L; (13) L=L->next; (14) free(Q); 解：a. (11) (3) (14) b. (10) (12) (8) (3) (14) c. (10) (12) (7) (3) (14) d. (12) (11) (3) (14) e. (9) (11) (3) (14) 2.8 已知P结点是某双向链表的中间结点，试从下列提供的答案中选择合适的语句序列。 a. 在P结点后插入S结点的语句序列是_______________________。 b. 在P结点前插入S结点的语句序列是_______________________。 c. 删除P结点的直接后继结点的语句序列是_______________________。 d. 删除P结点的直接前驱结点的语句序列是_______________________。 e. 删除P结点的语句序列是_______________________。 (1) P->next=P->next->next; (2) P->priou=P->priou->priou; (3) P->next=S; (4) P->priou=S; (5) S->next=P; (6) S->priou=P; (7) S->next=P->next; (8) S->priou=P->priou; (9) P->priou->next=P->next; (10) P->priou->next=P; (11) P->next->priou=P; (12) P->next->priou=S; (13) P->priou->next=S; (14) P->next->priou=P->priou; (15) Q=P->next; (16) Q=P->priou; (17) free(P); (18) free(Q); 解：a. (7) (3) (6) (12) b. (8) (4) (5) (13) c. (15) (1) (11) (18) d. (16) (2) (10) (18) e. (14) (9) (17) 2.9 简述以下算法的功能。 (1) Status A(LinkedList L) { //L是无表头结点的单链表 if(L && L->next) { Q=L; L=L->next; P=L; while(P->next) P=P->next; P->next=Q; Q->next=NULL; } return OK; } (2) void BB(LNode *s, LNode *q) { p=s; while(p->next!=q) p=p->next; p->next =s; } void AA(LNode *pa, LNode *pb) { //pa和pb分别指向单循环链表中的两个结点 BB(pa,pb); BB(pb,pa); } 解：(1) 如果L的长度不小于2，将L的首元结点变成尾元结点。 (2) 将单循环链表拆成两个单循环链表。 2.10 指出以下算法中的错误和低效之处，并将它改写为一个既正确又高效的算法。 Status DeleteK(SqList &a,int i,int k) { //本过程从顺序存储结构的线性表a中删除第i个元素起的k个元素 if(i<1||k<0||i+k>a.length) return INFEASIBLE;//参数不合法 else { for(count=1;count //删除第一个元素 for(j=a.length;j>=i+1;j--) a.elem[j-i]=a.elem[j]; a.length--; } return OK; } 解： Status DeleteK(SqList &a,int i,int k) { //从顺序存储结构的线性表a中删除第i个元素起的k个元素 //注意i的编号从0开始 int j; if(i<0||i>a.length-1||k<0||k>a.length-i) return INFEASIBLE; for(j=0;j<=k;j++) a.elem[j+i]=a.elem[j+i+k]; a.length=a.length-k; return OK; } 2.11 设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。 解： Status InsertOrderList(SqList &va,ElemType x) { //在非递减的顺序表va中插入元素x并使其仍成为顺序表的算法 int i; if(va.length==va.listsize)return(OVERFLOW); for(i=va.length;i>0,x va.elem[i]=va.elem[i-1]; va.elem[i]=x; va.length++; return OK; } 2.12 设 ()m a a A ,,1 =和()n b b B ,,1 =均为顺序表，A '和B '分别为A 和B 中除去最大共同前 缀后的子表。若 ='='B A 空表，则B A =；若A '=空表，而≠'B 空表，或者两者均不为空表，且A ' 的首元小于B '的首元，则B A <；否则B A >。试写一个比较A ，B 大小的算法。 解： Status CompareOrderList(SqList &A,SqList &B) { int i,k,j; k=A.length>B.length?A.length:B.length; for(i=0;i } if(A.length>k) j=1; if(B.length>k) j=-1; if(A.length==B.length) j=0; return j; } 2.13 试写一算法在带头结点的单链表结构上实现线性表操作Locate(L,x); 解： int LocateElem_L(LinkList &L,ElemType x) { int i=0; LinkList p=L; while(p&&p->data!=x){ p=p->next; i++; } if(!p) return 0; else return i; } 2.14 试写一算法在带头结点的单链表结构上实现线性表操作Length(L)。 解： //返回单链表的长度 int ListLength_L(LinkList &L) { int i=0; LinkList p=L; if(p) p=p-next; while(p){ p=p->next; i++; } return i; } 2.15 已知指针ha和hb分别指向两个单链表的头结点，并且已知两个链表的长度分别为m和n。试写一算法将这两个链表连接在一起，假设指针hc指向连接后的链表的头结点，并要求算法以尽可能短的时间完成连接运算。请分析你的算法的时间复杂度。 解： void MergeList_L(LinkList &ha,LinkList &hb,LinkList &hc) { LinkList pa,pb; pa=ha; pb=hb; while(pa->next&&pb->next){ pa=pa->next; pb=pb->next; } if(!pa->next){ hc=hb; while(pb->next) pb=pb->next; pb->next=ha->next; } else{ hc=ha; while(pa->next) pa=pa->next; pa->next=hb->next; } } 2.16 已知指针la和lb分别指向两个无头结点单链表中的首元结点。下列算法是从表la中删除自第i个元素起共len个元素后，将它们插入到表lb中第i个元素之前。试问此算法是否正确？若有错，请改正之。 Status DeleteAndInsertSub(LinkedList la,LinkedList lb,int i,int j,int len) { if(i<0||j<0||len<0) return INFEASIBLE; p=la; k=1; while(k q=p; while(k<=len){ q=q->next; k++; } s=lb; k=1; while(k s->next=p; q->next=s->next; return OK; } 解： Status DeleteAndInsertSub(LinkList &la,LinkList &lb,int i,int j,int len) { LinkList p,q,s,prev=NULL; int k=1; if(i<0||j<0||len<0) return INFEASIBLE; // 在la表中查找第i个结点 p=la; while(p&&k prev=p; p=p->next; k++; } if(!p)return INFEASIBLE; // 在la表中查找第i+len-1个结点 q=p; k=1; while(q&&k q=p->next; k++; } if(!q)return INFEASIBLE; // 完成删除，注意，i=1的情况需要特殊处理 if(!prev) la=q->next; else prev->next=q->next; // 将从la中删除的结点插入到lb中 if(j=1){ q->next=lb; lb=p; } else{ s=lb; k=1; while(s&&k s=s->next; k++; } if(!s)return INFEASIBLE; q->next=s->next; s->next=p; //完成插入 } return OK; } 2.17 试写一算法，在无头结点的动态单链表上实现线性表操作Insert(L,i,b)，并和在带头结点的动态单链表上实现相同操作的算法进行比较。 2.18试写一算法，实现线性表操作Delete(L,i)，并和在带头结点的动态单链表上实现相同操作的算法进行比较。 2.19 已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一高效的算法，删除表中所有 值大于mink且小于maxk的元素（若表中存在这样的元素），同时释放被删结点空间，并分析你的算法的时间复杂度（注意，mink和maxk是给定的两个参变量，它们的值可以和表中的元素相同，也可以不同）。 解： Status ListDelete_L(LinkList &L,ElemType mink,ElemType maxk) { LinkList p,q,prev=NULL; if(mink>maxk)return ERROR; p=L; prev=p; p=p->next; while(p&&p->data if(p->data<=mink){ prev=p; p=p->next; } else{ prev->next=p->next; q=p; p=p->next; free(q); } } return OK; } 2.20 同2.19题条件，试写一高效的算法，删除表中所有值相同的多余元素（使得操作后的线性表中所有元素的值均不相同），同时释放被删结点空间，并分析你的算法的时间复杂度。 解： void ListDelete_LSameNode(LinkList &L) { LinkList p,q,prev; p=L; prev=p; p=p->next; while(p){ prev=p; p=p->next; if(p&&p->data==prev->data){ prev->next=p->next; q=p; p=p->next; free(q); } } } 2.21 试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表 ()n a a ,,1 逆置为 ()1,,a a n 。 解： // 顺序表的逆置 Status ListOppose_Sq(SqList &L) { int i; ElemType x; for(i=0;i L.elem[i]=L.elem[L.length-1-i]; L.elem[L.length-1-i]=x; } return OK; } 2.22 试写一算法，对单链表实现就地逆置。 解： // 带头结点的单链表的逆置 Status ListOppose_L(LinkList &L) { LinkList p,q; p=L; p=p->next; L->next=NULL; while(p){ q=p; p=p->next; q->next=L->next; L->next=q; } return OK; } 2.23 设线性表()m a a a A ,,,21 =，()n b b b B ,,,21 =，试写一个按下列规则合并A ，B 为线性表 C 的算法，即使得 ()n m m m b b b a b a C ,,,,,,,111 += 当n m ≤时； ()m n n n a a b a b a C ,,,,,,,111 += 当n m >时。 线性表A ，B 和C 均以单链表作存储结构，且C 表利用A 表和B 表中的结点空间构成。注意：单链表的长度值m 和n 均未显式存储。 解： // 将合并后的结果放在C表中，并删除B表 Status ListMerge_L(LinkList &A,LinkList &B,LinkList &C) { LinkList pa,pb,qa,qb; pa=A->next; pb=B->next; C=A; while(pa&&pb){ qa=pa; qb=pb; pa=pa->next; pb=pb->next; qb->next=qa->next; qa->next=qb; } if(!pa)qb->next=pb; pb=B; free(pb); return OK; } 2.24 假设有两个按元素值递增有序排列的线性表A和B，均以单链表作存储结构，请编写算法将A表和B 表归并成一个按元素值递减有序（即非递增有序，允许表中含有值相同的元素）排列的线性表C，并要求利用原表（即A表和B表）的结点空间构造C表。 解： // 将合并逆置后的结果放在C表中，并删除B表 Status ListMergeOppose_L(LinkList &A,LinkList &B,LinkList &C) { LinkList pa,pb,qa,qb; pa=A; pb=B; qa=pa; // 保存pa的前驱指针 qb=pb; // 保存pb的前驱指针 pa=pa->next; pb=pb->next; A->next=NULL; C=A; while(pa&&pb){ if(pa->data qa=pa; pa=pa->next; qa->next=A->next; //将当前最小结点插入A表表头 A->next=qa; } else{ qb=pb; pb=pb->next; qb->next=A->next; //将当前最小结点插入A表表头 A->next=qb; } } while(pa){ qa=pa; pa=pa->next; qa->next=A->next; A->next=qa; } while(pb){ qb=pb; pb=pb->next; qb->next=A->next; A->next=qb; } pb=B; free(pb); return OK; } 2.25 假设以两个元素依值递增有序排列的线性表A和B分别表示两个集合（即同一表中的元素值各不相同），现要求另辟空间构成一个线性表C，其元素为A和B中元素的交集，且表C中的元素有依值递增有序排列。试对顺序表编写求C的算法。 解： // 将A、B求交后的结果放在C表中 Status ListCross_Sq(SqList &A,SqList &B,SqList &C) { int i=0,j=0,k=0; while(i if(A.elem[i] else if(A.elem[i]>B.elem[j]) j++; else{ ListInsert_Sq(C,k,A.elem[i]); i++; k++; } } return OK; } 2.26 要求同2.25题。试对单链表编写求C的算法。 解： // 将A、B求交后的结果放在C表中，并删除B表 Status ListCross_L(LinkList &A,LinkList &B,LinkList &C) 网工 一、单选 1.在OSI七层参考模型中，可以完成加密功能的是__________ A．物理层B。传输层C。会话层D。表示层 2. 计算机中用__________表示二进制数的长度 A．字B。字节C。字长 D.二进制位 3. 在OSIris七层参考模型中，网络层的功能主要是_________ A. 在信道上传输原始的比特流 B．确保到达对方的各段信息正确无误 C 确定数据包从源端到目的端如何选择路由 D 加强物理层数据传输原始比特流的功能并且进行流量调控 4. 如果鼠标器突然失灵，则可用组合键__________来结束一个正在运行的应用程序A．Alt+F4 B。Ctrl+F4 C。Shift+F4 D。Alt+Shift+F4 5. 以太网的典型逻辑拓扑结构是__________ A. 星型B。总线型C。环型D。网状 6. 物理层的主要功能是_________ A. 物理地址定义 B。建立端到端连接 C。在终端设备间传送比特流，定义了电压、接口、电缆标准和传输距离等 D．将数据从一端主机传送到另外一端主机 7. IP地址10.1.0.11的网络部分是_________ A. 10 B.10.1 C.10.1.0 D.以上都不对 8. 一个子网网段地址为10.32.0.0掩码为255.224.0.0的网络，它运行的最大主机地址是___________ A. 10.32.254.254 B.10.32.255.254 C．10.63.255.254 D。10.63.255.255 9. __________是指在一条通信线路中可以同时双向传输数据的方法 A．单工通信B。半双工通信C。同步通信D。全双工通信 10. 130.11.35.1/16默认是__________类网络的IP地址 A．B类B。D类C。E类D。F类 11.交换机路由器上任一命令视图下，键入_________键可以获取该命令视图下所有的命令及其简单描述 A．？B。！C。/ D. \ 12. Cisco 2950交换机清除配置信息的命令是__________ A. delete B. clear C.erase nvram D. format 13、交换机通过_________转发和过滤数据帧 A．Word表B。Excel表C。MAC地址表D。Access表 14. 路由表中不包含哪些项__________ A. MAC地址B。子网掩码C。目的网络地址D。下一跳地址 15. 思科路由器保存当前配置的命令是_________ A．write C。save C.copy D。reset 16. 公司处在单域的环境中，你是域的管理员，公司有两个部门：销售部和市场部，每个部门在活动目录中有一个相应的OU，分别是SALES和MARKET。有一个用户TOM要从市 16 void Descend(int &x, int &y, int &z) { int t; if(x while(result[i].sport!=NULL) { switch(result[i].schoolname) { case 'A': score[0].totalscore+=result[i].score; if(result[i].gender==male) score[0].malescore+=result[i].score; else score[0].femalescore+=result[i].score; break; case 'B': score[1].totalscore+=result[i].score; if(result[i].gender==male) score[1].malescore+=result[i].score; else score[1].femalescore+=result[i].score; break; case 'C': score[2].totalscore+=result[i].score; if(result[i].gender==male) score[2].malescore+=result[i].score; else score[2].femalescore+=result[i].score; break; case 'D': score[3].totalscore+=result[i].score; if(result[i].gender==male) score[3].malescore+=result[i].score; else score[3].femalescore+=result[i].score; break; case 'E': score[4].totalscore+=result[i].score; if(result[i].gender==male) score[4].malescore+=result[i].score; else score[4].femalescore+=result[i].score; break; } i++; } for(s='A';s<='E';s++) { printf("School %c:\n",s); printf("Total score of male:%d\n",score[i].malescore); printf("Total score of female:%d\n",score[i].femalescore); printf("Total score of all:%d\n\n",score[i].totalscore); } } 19 Status Series(int ARRSIZE, int a[]) 一、选择题： 1. 下列关于“隧道”的表述中错误的是（D）。 A.IP6数据报文封装入IPv4数据报文中 B.隧道具有一个入口和一个出口 C.隧道具有透明性，允许IPv6主机之间的通信 D.IPv6封装IPv4的数据报 2. 对等不适合构建在（ C ）。 A.10台以下计算机互连 B.小范围的互连 C.大规模的互连 D.小型办公室 3. 下列关于P2P的描述中不正确的是（B ）。 A.P2P技术通过在系统之间的直接交换实现计算机资源和服务的共享 B.P2P模型基于静态索引的服务器地址 C.P2P目前被广泛使用的例子是BT D.P2P技术是对等网络应用的新创新 4. B/S模式是（ D ）。 A.一种“胖”型系统 B.B指的是前台的客户机 C.与C/S模式同时产生的 D.使用三层或更多层的结构，具有成本低，易于改动和更新的优点 5. 在OSI参考模型中支持高层互连的设备是（C ）。 A.网桥 B.集线器 C.网关 D.路由器 6. 下列选项中（D ）不是安全需求分析中必须要明确的。 A. 网络用户的安全级别及其权限 B. 应用系统安全要求 C. 采用什么样的杀毒软件 D. 安全硬件系统的评估 7. 下列选项中（B ）不是标书的内容。 A. 参评方案一览表 B. 中标后对方应支付价格表 C. 系统集成方案 D. 设备配置及参数一览表 8. 通信量要求应该是从（A）出发。 A. 单位网络应用量的要求 B. 可以获得的最高带宽 C. 花费最少 D. 网络带宽的价格 9. 下列对于工程投标的描述中，不正确的是（A）。 A.投标文件不一定要严格遵循招标文件中的各项规定 B.投标人应该对招标项目提出合理的投标报价 C.投标人的各种商务文件、技术文件等应依据招标文件要求齐备 D.投标文件还应按招标人的要求进行密封、装订，按指定的时间、地点和方式递交，否 则投标文件将不会被接受 二、填空题： 1. 网络工程的整个建设阶段分为规划、设计、实施和运行维护。 2. 系统集成的定义是这样的：根据一个复杂的信息系统或子系统的要求 把多种产品和技术验明并连接入一个完整的解决方案的过程。整个系统集成包括软件集成、硬件集成和网络系统集成。 3. 在网络各层的互连设备中，中继器工作在物理层，集线器工作在物理 【题目】若两棵二叉树T1和T2皆为空，或者皆不空且T1的左、右子树和T2的左、右子树分别相似，则称二叉树T1和T2相似。试编写算法，判别给定两棵二叉树是否相似。 二叉链表类型定义： typedef struct BiTNode { TElemType data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; **********/ Status Similar(BiTree T1, BiTree T2) /* 判断两棵二叉树是否相似的递归算法*/ { if(!T1&&!T2)//同为空时，两树相似 return TRUE; else if(T1&&T1){ if(Similar(T1 -> lchild,T2 -> lchild) && Similar(T1 -> rchild,T2 -> rchild)) //两树都不为空时，判断左右子树是否相似 return TRUE; else return FALSE; }else//以上两种情况都不符合，就直接返回FALSE return FALSE; } /********** 【题目】编写递归算法，求对二叉树T先序遍历时 第k个访问的结点的值。 二叉链表类型定义： typedef struct BiTNode { TElemType data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; **********/ TElemType PreOrder(BiTree T, int &k) { TElemType x='#'; if(T==NULL)return '#'; if(k==1)return T->data; if(T->lchild!=NULL) { k--; x=PreOrder(T->lchild,k); } if(T->rchild!=NULL&&x=='#') 网络工程师考试试题（附答案） 二、多项选择题 1.某全双工网卡标有"100",关于该网卡的说法正确的有( ) A. 该网卡可以用来接双绞线 B. 该网卡可以用来接光缆 C. 该网卡最大传输速度为100 D. 该网卡最大传输速度为200 E. 该网卡最大传输速度为1000 2.在一般情况下, 下列关于局域网与广域网说法正确的有( ) A. 局域网比广域网地理覆盖范围大 B. 广域网比局域网速度要快得多 C. 广域网比局域网计算机数目多 D. 局域网比广域网误码率要低 E. 局域网不能运行协议 3.解决地址资源紧缺问题的办法有( ) A. 使用网页服务器 B. 使用代理服务器 C. 多台计算同时共用一个地址上网 D. 使用地址转换 E. 升级到6 4.在未进行子网划分的情况下,下列各项中属于网络地址的有( ) A. 10.0.0.0 B. 100.10.0.0 C. 150.10.10.0 D. 200.200.0.0 E. 200.200.200.0 5.网络按通信方式分类，可分为（）。 A. 点对点传输网络 B. 广播式传输网络 C. 数据传输网络 D. 对等式网络 6.计算机网络完成的基本功能是（）。 A. 数据处理 B. 数据传输 C. 报文发送 D. 报文存储 7.计算机网络的安全目标要求网络保证其信息系统资源的完整性、准确性和有限的传播范 围，还必须保障网络信息的（），以及网络服务的保密性。 A. 保密性 B. 可选择性 C. 可用性 D. 审查性 8.下列关于异步传输模式的描述正确的是（）。 A. 固定信元长度为53字节 B. 提供的参数 C. 一次群接入支持48条用用户信道和一条信令信道 D. 物理传输媒体可以是光纤 9.光纤分布式数据接口的特点是（）。 A. 利用单模光纤进行传输 B. 使用有容错能力的双环拓扑 在程序的执行过程中， Cache与主存的地址映射是由（1）完成的。 (1)A.操作系统 B.程序员调度 C.硬件自动 D.用户软件 【答案】C 【解析】 cache是高速缓冲存储器，作为CPU与主存之间的高速缓冲，有存储容量小，成本大，速度快的特点，存放经常被CPU访问的内容。cache和主存之间的映射由硬件自动完成。 某四级指令流水线分别完成取指、取数、运算、保存结果四步操作。若完成上述操作的时间依次为 8ns、9ns、4ns、8ns，则该流水线的操作周期应至少为（2）ns。 (2)A.4 B.8 C.9 D.33 【答案】C 【解析】 内存按字节编址。若用存储容量为 32Kx8bit 的存储器芯片构成地址从A0000H到DFFFFH的内存，则至少需要（3）片芯片。 (3)A.4 B.8 C.16 D.32 【答案】B 【解析】 存储区域空间为：DFFFF-A0000+1=40000H。 计算机系统的主存主要是由（4）构成的。 (4)A.DRAM B.SRAM C.Cache D.EEPROM 【答案】A 【解析】 DRAM动态随机存取存储器，最为常见的系统内存。为了保持数据，DRAM必须周期性刷新。 计算机运行过程中，CPU 需要与外设进行数据交换。采用（5）控制技术时，CPU与外设可并行工作。 (5)A.程序查询方式和中断方式 B.中断方式和 DMA 方式 C.程序查询方式和 DMA 方式 D.程序查询方式、中断方式和 DMA 方式【答案】B 【解析】 程序查询方式是按顺序执行的方式，由CPU全程控制。因此不能实现外设与CPU的并行工作。中断方式，在外设做好数据传送之前，CPU可做自己的事情。发出中断请求之后，CPU 响应才会控制其数据传输过程，因此能一定程度上实现CPU和外设的并行。而DMA方式由DMAC控制器向CPU申请总线的控制权，在获得CPU的总线控制权之后，由DMAC代替CPU控制数据传输过程。 李某购买了一张有注册商标的应用软件光盘，则李某享有（6）。 (6) A.注册商标专用权 B.该光盘的所有权 C.该软件的著作权 D.该软件的所有权 【答案】B 【解析】 购买光盘，只拥有光盘的所有权。 某软件项目的活动图如下图所示，其中顶点表示项目里程碑，连接顶点的边表示包含的活动，边上的数字表示活动的持续时间（天）。完成该项目的最少时间为（7）。由于某种原因，现在需要同一个开发人员完成BC和BD，到完成该项目如最少时闻为（8）天。 (7)A.11 B.18 C.20 D.21 (8)A.11 B.18 C.20 D.21 【答案】B C 【解析】 第一章绪论 一、填空题 1．数据是描述客观事物的数、字符以及所有能输入到计算机且能够被计算机程序加工处理的符号集合。____数据元素_____是数据的基本单位；____数据项_______是数据的最小单位。通常被计算机加工处理的数据不是孤立无关的，而是彼此之间存在着某种联系，将这种数据间的联系称为____结构____。 2．数据结构进行形式化定义时，可以从逻辑上认为数据结构DS是_____数据元素的有限集____的集合D和D上____关系的有限集_____的集合R所构成的二元组：DS=（D，R）。 3． 4．一个算法的时间复杂度通常用问题规模大小的函数来表示，当一个算法的时间复杂度与问题规模n大小无关时，则表示为____O(1)______；成正比关系时，则表示为_____O(n)______；成对数关系时，则表示为 ____O(log2n)_______；成平方关系时，则表示为____O(n2)______。 5．数据结构的逻辑结构包括_____线性结构________、树型结构和图型结构三种类型，其中树型结构和图型结构合称为______非线性结构_______；数据结构的存储结构主要包括____顺序________和______链式______两种类型。 6．线性结构的特点是：第一个结点___无____前驱结点，其余结点有且仅有__一_____个前驱结点；最后一个结点__无_____后继结点，其余每个结点有且仅有___一____个后继结点。 7．树型结构的特点是：根结点没有__前驱______结点，其余每个结点有且仅有_____一个___个前驱结点；叶子结点_____无____后继结点，其余结点可以有___任意______个后继结点。 8．图型结构的特点是：每个结点可以有____任意_____个前驱结点和后继结点。 9．程序段for（i=1，s=0；s 网络工程师历年考试试题及答案(一) https://www.doczj.com/doc/d68717947.html,work Information Technology Company.2020YEAR 网络工程师历年考试试题及答案（一） 网络工程师考试属于全国计算机技术与软件专业技术资格考试（简称计算机软件资格考试）中的一个中级考试。考试不设学历与资历条件，也不论年龄和专业，考生可根据自己的技术水平选择合适的级别合适的资格，但一次考试只能报考一种资格。考试采用笔试形式，考试实行全国统一大纲、统一试题、统一时间、统一标准、统一证书的考试办法。计算机与网络知识与网络系统设计与管理，笔试安排在一天之内。以下是小编整理的网络工程师历年考试试题及答案，希望对大家能有所帮助。 01．下列一组数据中的最大数是______。（A） A．311(8) B．C7(16) C．11001000(2) D．200(10) 02．PowerPoint中，有关选定幻灯片的说法中错误的是______。（D） A．在浏览视图中单击幻灯片，即可选定。 B．如果要选定多张不连续幻灯片，在浏览视图下按CTRL 键并单击各张幻灯片。 C．如果要选定多张连续幻灯片，在浏览视图下，按下shift 键并单击最后要选定的幻灯片。 D．在幻灯片视图下，也可以选定多个幻灯片。 03．以下哪个路由表项需要由网络管理员手动配置________。 (A ) A．静态路由 B．直接路由 C．动态路由 D．以上说法都不正确 04．以下命令中哪一个命令是配置Cisco 1900系列交换机特权级密码________。(A) A．enable password cisco level 15 B．enable password csico C．enable secret csico D．enable password level 15 05．以下哪个命令可以保存路由器RAM中的配置文件到NVRAM中________。（C） A．copy running-config tftp B．copy startup-config tftp C．copy running-config startup-config D．copy startup-config running-config 特别提示：请诚信应考,考试违纪或作弊将带来严重后果！ 成都理工大学工程技术学院 2009－2010学年第二学期 《计算机网络工程》试卷A 注意事项：1. 考前请将密封线内的各项内容填写清楚； 2. 所有答案请直接答在答题纸上； 3．考试形式：开卷； 4. 本试卷共三大题，满分100分，考试时间120分钟。 题号一二三总分 分数 阅卷人 一、填空题(每空1分，共15分) 1. OSI体系结构从下往上依次为物理层、__数据链路层___、网络层__、_传输层___、会话层___、_表示层____和_应用层____ 。 2. 目前以太网最常用的传输媒体是__双绞线_______ 。 3．数据链路层使用的信道主要有_______点对点____、_广播__________。 4.CSMA/CD协议的以太网只能工作在_______半双工____通信方式。 5.在以太网中将设备连接在一起可能使用的是具有物理星型拓扑的10BASE-T；然而，这些设备正在用_________逻辑总线型__拓扑进行通信。 6．ARP是解决_________同一局域网__主机或路由器的IP地址和硬件地址的映射问题。7．Ping命令是利用网络层的______ICMP____协议来实现回送请求和回送应答报文。8．OSPF路由协议的度量值（METRIC）是____链路花费_______。 二、不定项选择题 (每题2分，共50分) 1. 因特网使用的互联协议是( B ) A.IPX协议 B.IP协议 C.AppleTalk协议 https://www.doczj.com/doc/d68717947.html,BEUI协议 2.在WINDOW 2000中，查看arp高速缓存表中IP地址和MAC地址的对应项的命令是( A ) 第一章绪论 1．下面是几种数据的逻辑结构S=(D，R)，分别画出对应的数据逻辑结构，并指出它们分别属于何种结构。 D={a，b，c，d，e，f} R={r} (a) r={ 2017年4月高等教育自学考试全国统一命题考试 网络工程试卷 (课程代码04749) 本试卷共6页，满分l00分，考试时间l50分钟。 考生答题注意事项： 1．本卷所有试题必须在答题卡上作答。答在试卷上无效，试卷空白处和背面均可作草稿纸。 2．第一部分为选择题。必须对应试卷上的题号使用2B铅笔将“答题卡”的相应代码涂黑。 3．第二部分为非选择题。必须注明大、小题号，使用0．5毫米黑色字迹签字笔作答。 4．合理安排答题空间，超出答题区域无效。 第一部分选择题(共40分) 一、单项选择题(本大题共20小题，每小题2分。共40分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题卡”的相应代码涂黑。错涂、多涂或未涂均无分。 1．下列协议中，不属于应用层的是 A．FTP B．OSPF C．SMTP D．Telnet 2．下列有关计算机网络技术的叙述中，错误的是 A．常用的有线传输技术有ADSL、El、DDN、SDH等 B．以太网和WLAN能够承载IP数据报 C．RIP、OSPF、BGP、DNS属于IP路由协议 D．HTTP、TFTP、SNMP、SMTP属于应用层协议 3．下列关于PPPoE接入方式的桥接ADSL Modem(RFC2516)叙述中，错误的是 A．PPP连接建立在ADSL Modem和BRAS之间 B．用户主机与ADSLModem可以使用以太网连接 C．ATM PVC虚连接建立在ADSL Modem和BRAS之间 D．用户主机的公网IP地址由BRAS动态分配 4．下列关于DDN(数字数据网)的叙述中，错误的是 A．DDN是网状拓扑结构 B．DDN的主干传输为光纤传输 C．DDN只能采用点对点的专用数据线路 D．DDN路由自动迂回，保证链路高可用率 5．PAP(口令认证协议)需要握手的次数是 A．一次 B．两次 C．三次 D．四次 6．透明网桥解决环路问题所使用的算法是 A.扩散 B．最短路径优先 C．汇聚树(Sink Tree) D．生成树(Spanning Tree) 7．下列属性中，不属于WLAN的是 A．工作在ISM频段 数据结构题集答案 数据结构题集 第一章绪论 一、单选题 1.在数据结构中，从逻辑上可以把数据结构分成【 C 】。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 2.数据结构在计算机内存中的表示是指【 A 】。 A.数据的存储结构 B.数据结构 C.数据结构的逻辑结构 D.数据元素之间的关系 3. 【 A 】是数据的最小单位，【 B 】是数据的基本单位。 A.数据项 B.数据元素 C.信息项 D.表元素 4. 计算机所处理数据一般具有某种内在联系，这是指【 B 】。 A.数据与数据之间存在某种关系 B.数据元素与数据元素之间存在某种关系 C.元素内部存在某种结构 D.数据项与数据项之间存在某种关系 5.算法分析的目的是【 C 】。 A.找出数据结构的合理性 B.研究输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性 6.在存储数据时，不仅要考虑存储各数据元素的值，而且还要存储【 C 】。 A.数据处理的方法 B.数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 7.算法分析的主要任务是分析【 D 】。 A.算法是否具有较好的可读性 B.算法中是否存储语法错误和逻辑错误 C.算法的功能是否符合设计要求 D.算法的执行时间与问题规模之间的关系。 8.数据的运算【 A 】。 A.效率与采用何种存储结构有关 B.是根据存储结构来定义的 C.有算术运算和关系运算两大类 D.必须用程序设计语言来描述 9.算法的计算量的大小称为算法的【 B 】。 A.效率 B.时间复杂度 C.现实性 D.难度 10.连续存储分配时，存储单元的地址【A 】。 A.一定连续 B.一定不连续 C.不一定连续 D.部分连续，部分不连续 二、判断题 1.数据元素是数据结构的最小单位【.×】。 2.数据的逻辑结构说明数据元素之间的顺序关系，它依赖于计算机的存储结构【×.】。 3.数据的逻辑结构指数据元素的各数据项之间的逻辑关系【×.】。 4.算法的优劣与算法的描述语言无关，但与使用的计算机有关【.×】。 5.数据结构的抽象操作的定义与具体实现有关【.×】。 数据结构试题 一、单项选择 1、若某线性表中最常用的操作是在最后一个元素之后插入和删除元素，则采用___________最节省运算时间. A、单链表 B、仅有头指针的单循环链表 C、仅有尾指针的单循环链表 D、双链表 2、哈夫曼树的带权路径长度WPL等于___________. A、除根以外的所有结点的权植之和 B、所有结点权值之和 C、各叶子结点的带权路径长度之和 D、根结点的值 3、设输入序列为1,2,3,4,5，借助一个栈不可能得到的输出序列是___________. A、1,2,3,4,5 B、1,4,3,2,5 C、4,1,3,2,5 D、1,3,2,5,4 4、20个结点的完全二叉树，其高度为___________. A、3 B、2 C、4 D、5 5、栈和队列都是___________. A、顺序存储的线性结构 B、链式存储的线性结构 C、限制存储点的线性结构 D、限制存储点的非线性结构 6、已知完全二叉树有30个结点，则整个二叉树有___________个度为1的结点. A、0 B、1 C、2 D、不确定 7、对于N个结点的完全无向图，其边数是___________ A、N B、N2 C、N(N-1)/2 D、N(N-1) 8、队列的特点是 A、先进先出 B、先进后出 C、后进先出 D、不进不出 9、连通分量是的极大连通子图。 A、有向图 B、树 C、无向图 D、图 10、现有一“遗传”关系：设x是y的父亲，则x可以把它的属性遗传给y。表示该遗传关系最适合的数据结构为.............................. A、向量 B、树 C、图 D、二叉树 11、栈和队列都是（）. A、线性结构 B、链式存储的线性结构 C、线性结构或非线性结构 D、非线性结构 12、二叉树第J层有（）个结点 A、J B、2J C、J+1 D、不能确定 13、若图G中（）是有向的，则称此图为有向图. 网络工程师考试试题（含答案） 一、单项选择题 1．在FTP协议中，控制连接是由（）主动建立的。 A．服务器端B．客户端C．操作系统D．服务提供商 【解析】 在FTP协议中，由客户端通过服务器的TCP21端口向服务器发起连接。常识！【正确答案】B 2．无线局域网（）标准IEEE802.11g规定的最大数据速率是（）。 A．1Mb/sB．11Mb/s C．5Mb/sD．54Mb/s 【正确答案】D 3．配置VLAN有多种方法，下面哪一条不是配置VLAN的方法？（）。A．把交换机端口指定给某个VLAN B．把MAC地址指定给某个VLAN C．由DHCP服务器动态地为计算机分配VLAN D．根据上层协议来划分VLAN 【解析】 配置VLAN的方法有很多种，就是没有通过DHCP动态划分的那一种。 【正确答案】C 4．关于多模光纤，下面的描述中描述错误的是。 A．多模光纤的芯线由透明的玻璃或塑料制成 B．多模光纤包层的折射率比芯线的折射率低 C．光波在芯线中以多种反射路径传播 D．多模光纤的数据速率比单模光纤的数据速率高 【正确答案】D 5．在Linux系统中，利用（）命令可以分页显示文件的内容。A．listB．catC．moreD．cp 【正确答案】C 6．软件权利人与被许可方签订一份软件使用许可合同。若在该合同约定的时间和地域范围内，软件权利人不得再许可任何第三人以此相同的方法使用该项软件，但软件权利人可以自己使用，则该项许可使用是。 A．独家许可使用B．独占许可使用 C．普通许可使用D．部分许可使用 【解析】 许可贸易实际上是一种许可方用授权的形式向被许可方转让技术使用权同时也让度一定市场的贸易行为。根据其授权程度大小，许可贸易可分为如下五种形式： (1)独占许可。它是指在合同规定的期限和地域内，被许可方对转让的技术享有独占的使用权，即许可方自己和任何第三方都不得使用该项技术和销售该技术项下的产品。所以这种许可的技术使用费是最高的。 (2)排他许可，又称独家许可；它是指在合同规定的期限和地域内，被许可方和许可方自己都可使用该许可项下的技术和销售该技术项下的产品，但许可方不得再将该项技术转让给第三方。排他许可是仅排除第三方面不排除许可方。 1、解决路由环问题的方法有(ABD) A.水平分割 B.路由保持法 C.路由器重启 D.定义路由权的最大值 2、下面哪一项正确描述了路由协议(C) A.允许数据包在主机间传送的一种协议 B.定义数据包中域的格式和用法的一种方式 C.通过执行一个算法来完成路由选择的一种协议 D.指定MAC地址和IP地址捆绑的方式和时间的一种协议 3、以下哪些内容是路由信息中所不包含的(A) A.源地址 B.下一跳 C.目标网络 D.路由权值 4、以下说法那些是正确的(BD) A.路由优先级与路由权值的计算是一致的 B.路由权的计算可能基于路径某单一特性计算， 也可能基于路径多种属性 C.如果几个动态路由协议都找到了到达同一目标网络的最佳路由, 这几 条路由都会被加入路由表中 D.动态路由协议是按照路由的路由权值来判断路由的好坏, 并且每一种路由协议的判断方法都是不一样的 5、I GP的作用范围是（C） A.区域内 B.局域网内 C.自治系统内 D.自然子网范围内 6、距离矢量协议包括（AB） A.RIP B.BGP C.IS-IS D.OSPF 7、关于矢量距离算法以下那些说法是错误的（A） A.矢量距离算法不会产生路由环路问题 B.矢量距离算法是靠传递路由信息来实现的 C.路由信息的矢量表示法是（目标网络，metric） D.使用矢量距离算法的协议只从自己的邻居获得信息 &如果一个内部网络对外的出口只有一个，那么最好配置 (A) A.缺省路由 B.主机路由 C.动态路由 9、BGP是在（D）之间传播路由的协议 A.主机 B.子网 C.区域(area) D.自治系统(AS) 10、在路由器中，如果去往同一目的地有多条路由，则决定最佳路由的因素有(AC) A.路由的优先级 B.路由的发布者 C.路由的metirc值 D.路由的生存时间 11、在RIP协议中，计算metric值的参数是(D) A.MTU B.时延 C.带宽 D.路由跳数 12、路由协议存在路由自环问题(A) A.RIP B.BGP C.OSPF D.IS-IS 13、下列关于链路状态算法的说法正确的是:(bc ) A.链路状态是对路由的描述 B.链路状态是对网络拓扑结构的描述 严蔚敏 数据结构C 语言版答案详解 第1章 绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解： ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={ 七、综合题：某大学计算中心有10个计算机机房（每个机房有50台计算机），部门1有20台计算机，部门2有 40台计算机，部门3有8台计算机，通过三层交换机与学校网络中心连接。另有三台服务器，分别提供WWW、E-mail、FTP服务。其中，每个计算机机房可以根据实际需要设置允许连接Internet的时间；FTP服务器仅对计算中心内部提供服务。现要求你综合本课程所学知识，完成下列内容（14分）： 1. 请为该计算机中心设计划分VLAN，以满足各方面的需要，并说明理由； 2. 学校网络中心分配给计算中心的IP地址为，请给出每个VLAN的IP地址分配方案（包括IP地 址范围、子网掩码）； 3. 根据题目中的要求，给出网络安全和访问控制的具体措施； 4. 对该网络的设计和管理提出自己的建议，并说明理由。 答：1．可以将计算机中心的网络划分为15个VLAN，其中10个计算机机房分别属于一个不同的VLAN，部门1、部门2、部门3各属一个VLAN，所有的服务器属于一个VLAN，另外一个VLAN用于与学校网络中心连接。这样划分VLAN，除了可以减少网络广播风暴、提高网络的性能和安全性外，还便于管理和维护，并且使得任课教师比较容易对机房中的计算机是否能访问Internet进行控制。（3分） 2．由于计算机中心主机的数量远远超过了网络中心提供的IP地址的数量，因此，计算机机房中所有计算机均采用内部IP地址，而通过路由器或三层交换机进行地址转换。具体的IP地址划分方案如下：（5分） 3．可以在路由器或三层交换机中通过扩展的访问控制列表来实现题目中要求的安全控制，对FTP服务器可以设置根据原IP地址和目的IP地址匹配的访问控制列表；而对计算机机房的所有计算机，可以设置根据时间段和源IP地址匹配的访问控制列表，使得不同机房可以在不同的时间段访问Internet。（3分）4．建议在网络中增设一台DHCP服务器，并在三层交换机或路由器中启用DHCP中继功能，使得所有VLAN 能够共用一台DHCP服务器，可以减轻IP地址的分配和管理的负担。另外，可以考虑在与网络中心连接部位安装防火墙，以加强对内部网络的安全保护。（3分） 六．应用题 正确 获得1.00分中的1.00分 标记题目 题干 中缀表达式：（a+b）*d+e/(f+a*d)+c的后缀表达式为：ab+d*efad+/*+c+ ( ) 选择一项： 对 错 反馈 正确的答案是“错”。 正确 此次提交得分：1.00/1.00。 题目2 正确 获得1.00分中的1.00分 标记题目 题干 若元素a,b,c,d,e,f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是（） 选择一项： a. b,c,a,e,f,d b. a,f,e,d,c,b c. d,c,e,b,f,a d. c,b,d,a,e,f correct feedback 正确答案是：a,f,e,d,c,b 正确 此次提交得分：1.00/1.00。 题目3 正确 获得1.00分中的1.00分 标记题目 题干 假设栈初始为空，将中缀表达式a/b+(c*d-e*f)/g转换为等价的后缀表达式的过程中，当扫描到f时，栈中的元素依次是（）。 选择一项： a. +（*— b. +(—* c. /+—* d. /+(*—* 反馈 correct feedback 正确答案是：+(—* 正确 此次提交得分：1.00/1.00。 题目4 正确 获得1.00分中的1.00分 标记题目 题干 一个栈的入栈序列为1，2，3，…，n，其出栈序列是p1，p2，p3，…，pn。如果p2=3，则 p3可能取值的个数是( )。 选择一项： a. 无法确定 b. n-3 c. n-2 d. n-1 反馈 correct feedback 正确答案是：n-1 正确 此次提交得分：1.00/1.00。 题目5 正确 获得1.00分中的1.00分 标记题目 题干 经过下列栈运算后，StackEmpty（S）的值是______。InitStack（S）；Push（S，a）；Push（S，b）；Pop（S，x）；Pop（S，y） 选择一项： a. a b. 1 c. b d. 0 反馈 correct feedback 正确答案是：1 正确网络工程测试试题和答案
数据结构题集c语言版答案严蔚敏吴伟民[1]
(完整版)网络工程试卷及答案
2016最新广工anyview数据结构答案
网络工程师考试试题(附答案)
2017年下半年 网络工程师 真题与答案详解
数据结构习题集
网络工程师历年考试试题及答案(一)
《计算机网络工程》试题及答案
数据结构习题集(积分)
04749+网络工程+201704+真题及答案
数据结构题集答案复习过程
数据结构习题集
网络工程师考试试题精选(含答案)rs
网络工程师面试题附答案
严蔚敏数据结构题集(C语言版)完整
《计算机网络工程》习题集及参考答案
数据结构题集
相关主题
文本预览