第1 章绪论
一、单项选择题
1．①B ②D。
2．C。
3．A。
4．A。
5．C A
6．C。
7．B
8．C
9．C
10．C
二、判断题（在各题后填写“√”或“×”）
1. 线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。（×）
2. 数据元素是数据的最小单位。(×)
3. 记录是数据处理的最小单位。( ×)
4. 算法就是程序。（×）
5. 数据的逻辑结构是指数据的各数据项之间的逻辑关系；(×)
6．数据的物理结构是指数据在计算机内的实际存储形式。(√)
7. 在顺序存储结构中，有时也存储数据结构中元素之间的关系。(×)
8. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( ×)
9. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址一定是不连续的。(×)
10. 数据的逻辑结构说明数据元素之间的
顺序关系,它依赖于计算机的储存结构.
( ×)
三、填空题
1. 逻辑结构物理结构操作（运算）算法
2. 集合线性结构树形结构图状结构或
网状结构
2. 没有1 没有1
4. 前驱1 后续任意多个
5．表示（又称映像）
6.顺序存储方式链式存储方式索引存储
方式散列存储方式
7．（1）逻辑特性（2）在计算机内部如何表示和实现（3）数学特性8．算法的时间复杂度和空间复杂度9．（1）有穷性（2）确定性（3）可行性
10. 1 log2n n n2 2n 实际不可计算高效
11. (n+3)(n-2)/2
12．①(1)1 (2)1 (3)f(m,n-1) (4)n ②9
13. o(log2n)。
四、应用题
1．解答：（1）图略。线性结构
（2）图略。树结构
（3）图略。图结构
2．将学号、姓名、平均成绩看成一个记录（元素，含三个数据项），将100个这样的记录存
于数组中。因一般无增删操作，故宜采用顺序存储。
typedef struct
{int num;//学号
char name[8];//姓名
float score;/平均成绩
}node；
node student[100];
3. 第一层FOR 循环判断n+1 次，往下执行n 次，第二层FOR 执行次数为
(n+(n-1)+(n-2)+…+1)，第三层循环体受第一层循环和第二层循环的控制，其执行次数如下
表：
i=1 2 3 4 …n-1 n
j=n j=n j=n j=n …j=n j=n
n-1 n-1 n-1 n-1 …n-1
…………
3 3 3
2 2
1
总执行次数为(1+2+…+n)+(2+3+…+n)+…+n=n*n(n+1)/2-n(n2-1)/6。在n=5 时，
f(5)=55，
执行过程中，输出结果为：
sum=15,sum=29,sum=41,sum=50,sum=5 5（每个sum= 占一行,为
节省篇幅，这里省去换行）。
4．解答：（１）int locate(dataytpe
A[1..n],dateytpe k)
{ i=1;
while ((i<=n)&&(A[i]!=k)) i++;
if (i<=n) return(i);
else return(o);
}
最坏时间复杂度T（n）=O(n).
（２）Void CZ_max(datatype A[n],x,y) { x=A[1]; y=A[1];
for(i=2;i<=n;I++)
if(x else if(y } 最坏情况时间复杂度T(n)=O(n). 第2 章线性表 一、单项选择题 1．B 2.A 3．C 4．C 5．.A 6．D 7. B 8. B 9．B 10.C 11．C 12．B 13．B 二、判断题（在各题后填写“√”或“×”） 1. 链表中的头结点仅起到标识的作用。(×) 2．线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。( √) 3．顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。( ×) 4. 对任何数据结构链式存储结构一定优于顺序存储结构。(×) 5. 所谓静态链表就是一直不发生变化的链表。( ×) 6. 线性表的特点是每个元素都有一个前驱和一个后继。( ×) 7. 循环链表不是线性表. ( ×) 8. 线性表只能用顺序存储结构实现。( ×) 9. 线性表就是顺序存储的表。( ×) 10. 链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结 构中效率高。(√) 三、填空题 1．必定不一定 2．头指针头结点指针域前驱结点指针域3．双向链表 4．n O(n) n/2 O(n) 5．. 单链表循环链表双向链表 6．指针 7．（n-1）/2 8．py->next=px->next; px->next=py 9. 4 2 10．i=1; i≤https://www.doczj.com/doc/962626537.html,st 11．(1)L->next=null ∥置空链表,然后将原链表结点逐个插入到有序表中 (2)p!=null ∥当链表尚未到尾，p 为工作指针 (3)q!=null ∥查p结点在链表中的插入位置，这时q 是工作指针。 (4)p->next=r->next ∥将p 结点链入链表 中 (5)r->next=p ∥r是q 的前驱，u 是下个待插入结点的指针。 12．(1)(A!=null && B!=null) ∥两均未空时循环 (2)A->element==B->element ∥两表中相等元素不作结果元素 (3)B=B->link ∥向后移动B表指针 (4)A!=null ∥将A 表剩余部分放入结果表 中 (5)last->link=null ∥置链表尾 四、应用题 1. 在线性表的链式存储结构中，头指针指链表的指针，若链表有头结点则是链表的头结点 的指针，头指针具有标识作用，故常用头指针冠以链表的名字。头结点是为了操作的统一、 方便而设立的，放在第一元素结点之前，其数据域一般无意义（当然有些情况下也可存放链 表的长度、用做监视哨等等），有头结点后， 对在第一元素结点前插入结点和删除第一 结点， 其操作与对其它结点的操作统一了。而且无论链表是否为空，头指针均不为空。首元结点也 就是第一元素结点，它是头结点后边的第一个结点。 2. 在单链表中不能从当前结点（若当前结点不是第一结点）出发访问到任何一个结点，链 表只能从头指针开始，访问到链表中每个结点。在双链表中求前驱和后继都容易，从当前结 点向前到第一结点，向后到最后结点，可以访问到任何一个结点。 3. 1）本算法功能是将双向循环链表结点的数据域按值自小到大排序，成为非递减（可能包括 数据域值相等的结点）有序双向循环链表。2）(1)r->prior=q->prior;∥将q 结点摘下，以便插入到适当位置。 (2)p->next->prior=q;∥（2）（3）将q结点插入 (3)p->next=q; (4)r=r->next;或r=q->next;∥后移指针，再将新结点插入到适当位置。 五、算法设计题 1. [题目分析] 在递增有序的顺序表中插入一个元素x，首先应查找待插入元素的位置。因 顺序表元素递增有序，采用折半查找法比顺序查找效率要高。查到插入位置后，从此位置直 到线性表尾依次向后移动一个元素位置，之后将元素x 插入即可。 void Insert（ElemType A[]，int size, ElemType x） ∥A 是有size 个元素空间目前仅有num （num 插入到线性表中，并保持线性表的有序性。{low=1；high=num；//题目要求下标从1 开始while（low<=high）∥对分查找元素x 的插入位置。 {mid=（low+high）/2； if（A[mid]==x）{low=mid+1；break；} else if（A[mid]>x）high=mid-1 ；else low=mid+1 ； } for（i=num；i>=low；i--）A[i+1]=A[i]；∥元素后移。 A[i+1]=x；∥将元素x 插入。 }算法结束。 [算法讨论] 算法中当查找失败（即线性表中无元素x）时，变量low在变量high的右 面（low=high+1）。移动元素从low 开始，直到num为止。特别注意不能写成for （i=low； i<=num；i++）A[i+1]=A[i]，这是一些学生容易犯的错误。另外，题中未说明若表中已有值 为x 的元素时不再插入，故安排在A[mid]= =x 时，用low（=mid+1）记住位置，以便后面 统一处理。查找算法时间复杂度为O（logn），而插入时的移动操作时间复杂度为O（n），若 用顺序查找，则查找的时间复杂度亦为O （n）。 2．解答：(1)顺序表 分析：将顺序表的第一个元素与最后一个元素互换，第二个元素与__________倒数第二个元素互换。 void invert(SeqList *L, int *num) { int j; ElemType tmp; for(j=0;j<=(*num-1)/2;j++) { tmp=L[j]; L[j]=L[*num-j-1]; L[*num-j-1]=tmp;} } (2)单链表 void invert(LinkList L) { Node *p, *q, *r; if(L->next ==NULL) return; /*链表为空*/ p=L->next; q=p->next; p->next=NULL; /* 摘下第一个结点，生成初始逆置表*/ while(q!=NULL) /* 从第二个结点起依次头插入当前逆置表*/ { r=q->next; q->next=L->next; L->next=q; q=r; } } 3．解答：(1)定位LOCATE(L，X) 在带头结点类单链表上实现的算法为： int locate_lklist(lklist head,datatype x) /*求表head中第一个值等于x的的序号，不存在这种结点时结果为0*/ {p=head->next;j=1; /*置初值*/ while((p!=NULL)&&(p->data!=x)) {p=p->next;j++}/*未达表结点又未找到值等于X 的结点时经，继续扫描*/ if (p->data = =x) return(j); else return(0); } 在无头结点的单链表上实现的算法为： int Wlocate(lklist head,datatype X) /*求表head中第一个值等于x的结点的序号。不存在这种结点时结果为0*/ {p=head; j=1; /*置初值*/ while((p!=NULL)&&(p->data!=x)) {p=p->next;j++}/*未达表结点又未找到值等于X 的结点时经，继续扫描*/ if( p->data = =X) return(j); else return(0); } (2)按序号查找find(L,i) 在带头结点的单链表上实现的算法为：pointer find_lklist(lklist head , int i); { j=1; p=head->next; while((j<1)&&(p!=NULL)){p=p->next; j++} if(i= = j) return(p); else return(NULL); } 在无头结点的单链表上实现的算法为：pointer find_lklist(lklist head , int i); { j=1; p=head; while((j<1)&&(p!=NULL)){p=p->next; j++} if(i= = j) return(p); else return(NULL); } (3)、插入INSERT(L，X，i) 在带头结点单链表上实现的算法为： void insert_lklist(lklist head,datatype x,int I) /*在表haed的第i 个位置上插入一人以x 为值的新结点*/ {p=find_lklist(head,i-1); /*先找第i-1 个结点*/ if(p= =NULL)reeor(“不存在第i 个位置”)/*若第i-1个结点不存在，退出*/ else{s=malloc(size);s->data=x /*否则生成新结点*/ s->next=p->next /*结点*p在链域值传给结点*s 的链域*/ p->next=s; /*修改*p 的链域*/ } } 在无头结点的单链表上实现的算法为：void Winsert(lklist head,dataytpe X,int i) /*在表haed的第i 个位置上插入一人以x 为值的新结点*/ {if(i<=0) error(“i<=0”); else{ s=malloc(size);s->data=X; /*否则生成新结点*/ if(i= =1){s->next=head;head=s;} else{ p=wfind_lklist(lklist head,i-1); if(p= =NULL) error(“i>n+1”); else{s->next=p->next;p->next=s;} } } (4)删除DELDTE(L,i) 在带头结点的单链表上实现的算法为：void delete_lklist(lklist head,int i) /*删除表head 的第i个结点*/ {p=find_lklist(head,i-1) /*先找待删结点的直接前驱*/ if((p!==NULL)&&(p->next!=NULL))/*若直接前趋存在且待结点存在*/ (q=p->next; /*q 指向待删结点*/ p->next=q->next/*摘除待结点*/; free(q);/*释放已摘除结点q*/ } else error(“不存在第i 个结点”)/*否则给出相关信息*/ } 在无头结点的单链表上实现的算法为：void Wdelete(lklist head,int i) /* 删除表head 的第i 个结点，若该链表仅有一个结点时，赋该结点指针NULL*/ {if(i<=0) error(“I＜＝0” else{if(i= =0){q=head;head=head->next;free(q);} else{p=wfind_lklist(head,i-1);/*找链表head 中第i-1 结点指针*/ if(p!=NULL)&&(p->next!=NULL) ｛q=p->next; p->next=q->next; free(q);｝else error(“不存在第I 个结点”)； ｝ ｝ ｝ 4．【解答】算法如下： LinkList merge(LinkList A, LinkList B, LinkList C) { Node *pa, *qa, *pb, *qb, *p; pa=A->next; /*pa表示A 的当前结点*/ pb=B->next; p=A; / *利用p 来指向新连接的表的表尾，初始值指向表A 的头结点*/ while(pa!=NULL && pb!=NULL) /*利 __________用尾插法建立连接之后的链表*/ { qa=pa->next; qb=qb->next; p->next=pa; /*交替选择表A 和表B 中的结点连接到新链表中；*/ p=pa; p->next=pb; p=pb; pa=qa; pb=qb; } if(pa!=NULL) p->next=pa; /*A 的长度大于B 的长度*/ if(pb!=NULL) p->next=pb; /*B 的长度大于A 的长度*/ C=A; Return(C); } 5. [题目分析] 在顺序存储的线性表上删除元素，通常要涉及到一系列元素的移动（删第i 个元素，第i+1 至第n个元素要依次前移）。本题要求删除线性表中所有值为item 的数据元 素，并未要求元素间的相对位置不变。因此可以考虑设头尾两个指针（i=1，j=n），从两端 向中间移动，凡遇到值item 的数据元素时，直接将右端元素左移至值为item的数据元 素位 置。 void Delete（ElemType A[ ]，int n） ∥A 是有n 个元素的一维数组，本算法删除A 中所有值为item 的元素。 {i=1；j=n；∥设置数组低、高端指针（下标）。while（i {while（i if（i if（i } [算法讨论] 因元素只扫描一趟，算法时间复杂度为O（n）。删除元素未使用其它辅助空间，最后线性表中的元素个数是j。若题目要求元素间相对顺序不变，请参见本章三、填 空题25 的算法。 6．分析设置两个指针，分别指向*S 及其后继，然后按循环链表特性，顺序往下查找*s 的 直接前趋，找到后删除； void DELETE_Xlklist(lklist S) {p=s; q=p->next; while (q->nest!=s) { p=q; q=q->next;} p->next=s; free(q); } 7．分析：在链表L 中依次取元素，若取出的元素是字母，把它插入到字母B 中，然后在L 中删除该元素；若取出的元素是数字，把它插入到数字链D 中，然后在L 中删除该元素。继 续取下一个元素，直到链表的尾部。最后B、D、L 中分别存放的是字母字符、数字字符和其 它字符。 设原表有头结点、头指针L，新建数字字符链D，字母字符链B，其它字符链R。 void DISM_lklist(lklist L,lklist D,lklist B,lklist R) { D =malloc(size of(int)); D ->next= D; /*建D循环链表头结点*/ B =malloc(sizeof(char)); B ->next= B; /*建B循环链表头结点*/ p= L;q=p->next; while(q!=null) {if((q->data<=’9’)&&(q->data>=’0’)) {p->next=q->next; /*在表L 中摘除q 结点*/ q->next= D ->next; D ->next=q; /*将q 结点插入D 中*/ q=p->next; /*移动q 指针*/ } else if (q->data<=’z’)&&(q->data>=’a’)||(q->data<=’z’)&&(q->data>=’a’)) {p->next=q->next; /*在表L 中删除q 结点*/ q->next= B ->next; B ->next=q; /*将q 结点插入B 中*/ q=p->next; /*移动q 指针*/ }else {p=q;q=p->next;} /*移动q 指针*/ } p->next=L;R=L; /*使R 为循环表*/ } 8．约瑟夫环问题 【解答】算法如下： typedef struct Node { int password; int num; struct Node *next; } Node,*Linklist; void Josephus() { Linklist L; Node *p,*r,*q; int m,n,C,j; L=(Node*)malloc(sizeof(Node)); /*初始化单向循环链表*/ if(L==NULL) { printf("\n链表申请不到空 间!");return;} L->next=NULL; r=L; printf("请输入数据n 的值(n>0):"); scanf("%d",&n); for(j=1;j<=n;j++) /*建立链表*/ { p=(Node*)malloc(sizeof(Node)); if(p!=NULL) { printf("请输入第%d个人的密码:",j); scanf("%d",&C); p->password=C; p->num=j; r->next=p; r=p; } } r->next=L->next; printf("请输入第一个报数上限值m(m>0):"); scanf("%d",&m); printf("**************************************** *\n"); printf("出列的顺序为:\n"); q=L; p=L->next; while(n!=1) /*计算出列的顺序*/ { j=1; while(j { q=p; /*q 为当前结点p 的前驱结点*/ p=p->next; j++; } printf("%d->",p->num); m=p->password; /*获得新密码*/ n--; q->next=p->next; /*p 出列*/ r=p; p=p->next; free(r); } printf("%d\n",p->num); } 第3 章栈和队列 一单项选择题 1. B A B 2．A 3. C 4.B 5. B 6. B 7. D 8. D 9. C 10．D 11.C 12. C 二、填空题 1．操作受限（或限定仅在表尾进行插入和删除操作）后进先出 2. 3 1 2 3．S×SS×S×× 4. 假溢出时大量移动数据元素 5．先进先出 6. s=(LinkedList)malloc(sizeof(LNode))；s->data=x;s->next=r->next；r->next=s；r=s； 7．栈 8．（rear-front+m）% m； 9．ls=NULL 10．p->data=x, ls=p 11．p->data, free(p) 12．p->data, p, lq->rear=p 三、应用题1．【解答】（1）顺序栈（top用来存放栈顶元素的下标） 判断栈S 空：如果S->top==-1表示栈空。判断栈S 满：如果S->top==Stack_Size-1表示栈满。 (2) 链栈（top 为栈顶指针，指向当前栈顶元素前面的头结点） 判断栈空：如果top->next==NULL 表示栈空。 判断栈满：当系统没有可用空间时，申请不到空间存放要进栈的元素，此时栈满。 2. 设操作数栈是opnd，操作符栈是optr，对算术表达式A-B*C/D-E↑F 求值，过程如下： 步骤opnd 栈optr 栈输入字符主要操作 初始# A-B*C/D-E↑F# PUSH(OPTR,’#’) 1 A # A-B*C/D-E↑F# PUSH(OPND,A) 2 A # - -B*C/D-E↑F# PUSH(OPTR,’-’) 3 AB # - B*C/D-E↑F# PUSH(OPND,B) 4 AB # - * *C/D-E↑F# PUSH(OPTR,’*’) 5 ABC # - * C/D-E↑F# PUSH(OPND,C) 6 AT(T=B*C) # - / /D-E↑F# PUSH(OPND,POP(OPND)*POP(OPND)) PUSH(OPTR,’/’) 7 ATD # - / D-E↑F# PUSH(OPND,D) 8 AT(T=T/D) T(T=A-T) # - # - -E↑F# x=POP(OPND);y=POP(OPND) PUSH(OPND,y/x); x=POP(OPND);y=POP(OPND); PUSH(OPND,y-x) PUSH(OPTR,’-’) 9 TE # - E↑F# PUSH(OPND,E) 10 TE # -↑↑F# PUSH(OPTR, ‘↑’) 11 TEF # -↑F# PUSH(OPND,F) 12 TE TS(S=E ↑ F) R(R=T-S) #- # # X=POP(OPND) Y=POP(OPND) POP(OPTR) PUSH(OPND,y↑x) x=POP(OPND) y=POP(OPND) POP(OPTR) PUSH(OPND,y-x) 3. 设栈S1 和栈S2共享向量V[1..m]，初始时，栈S1 的栈顶指针top[0]=0，栈S2 的栈顶 指针top[1]=m+1，当top[0]=0为左栈空，top[1]=m+1为右栈空；当top[0]=0并且 top[1]=m+1 时为全栈空。当top[1]-top[0]=1 时为栈满。 4. 设顺序存储队列用一维数组q[m]表示，其中m 为队列中元素个数，队列中元素在向量中 的下标从0到m-1。设队头指针为front，队尾指针是rear，约定front指向队头元素的前一位置，rear 指向队尾元素。当front 等于-1 时队空，rear等于m-1时为队满。由于队列 的性质（“删除”在队头而“插入”在队尾），所以当队尾指针rear 等于m-1 时，若front 不等于-1，则队列中仍有空闲单元，所以队列并不是真满。这时若再有入队操作，会造成假 “溢出”。其解决办法有二，一是将队列元素向前“平移”（占用0 至rear-front-1）；二是 将队列看成首尾相连，即循环队列 （0..m-1）。在循环队列下，仍定义front=rear 时为队空， 而判断队满则用两种办法，一是用“牺牲一个单元”，即rear+1=front（准确记是（rear+1） %m=front，m 是队列容量）时为队满。另一种解法是“设标记”方法，如设标记tag，tag 等于0 情况下，若删除时导致front=rear 为队空；tag=1情况下，若因插入导致 front=rear 则为队满。 四算法设计题 1．解：方法是先依次让单链表上的元素进栈，然后再依次出栈。 Void invert (lklist head) {LstackTp s; initstack(s); p= head; while (p<>null) {Push (s,p->data);p=p->next;} p=head; while(not emptystack(s)) {pop(s,p->data); p=p->next;} } 2. [题目分析]判断表达式中括号是否匹配，可通过栈，简单说是左括号时进栈，右括号时 退栈。退栈时，若栈顶元素是左括号，则新读入的右括号与栈顶左括号就可消去。如此下去， 输入表达式结束时，栈为空则正确，否则括号不匹配。 int EXYX(char E[],int n) //E[]是有n 字符的字符数组，存放字符串表达式，以‘#’结束。本算法判断表达式中圆 括号是否匹配。 {char s[30]; //s是一维数组，容量足够大，用作存放括号的栈。 int top=0; //top 用作栈顶指针。 s[top]= ‘#’; //‘#’先入栈，用于和表达式结束符号‘#’匹配。 int i=0; //字符数组E 的工作指针。 while(E[i]!= ‘#’) //逐字符处理字符表达式的数组。 switch(E[i]) {case‘(’: s[++top]=‘(’; i++ ; break ; case‘)’: if(s[top]==‘(’{top--; i++; break;} else{printf(“括号不配对”);exit(0);} case‘#’: if(s[top]==‘#’){printf(“括号配对\n”);return (1);} else {printf(“括号不配对\n”);return (0);} //括号不配对 default : i++; //读入其它字符，不作处理。} }//算法结束。 [算法讨论]本题是用栈判断括号匹配的特 例：只检查圆括号的配对。一般情况是检查花 括号（‘{’，‘}’）、方括号（‘[’，‘]’）和圆括号（‘（’，‘）’）的配对问题。编写算法中如 遇左括号（‘{’，‘[’，或‘（’）就压入栈中，如遇右括号（‘}’，‘]’，或‘）’），则与栈顶 元素比较，如是与其配对的括号（左花括号，左方括号或左圆括号），则弹出栈顶元素；否 则，就结论括号不配对。在读入表达式结束符‘#’时，栈中若应只剩‘#’，表示括号全部 配对成功；否则表示括号不匹配。 另外，由于本题只是检查括号是否匹配，故对从表达式中读入的不是括号的那些字符，一律未作处理。再有，假设栈容量足够大，因此入栈时未判断溢出。 3. （1）A和D 是合法序列，B和C 是非法序列。 （2）设被判定的操作序列已存入一维数组A 中。 int Judge(char A[]) //判断字符数组A 中的输入输出序列是否是合法序列。如是，返回true，否则返 回false。 {i=0; //i 为下标。 j=k=0; //j 和k 分别为I 和字母O 的的个数。 while(A[i]!=‘\0’) //当未到字符数组尾就作。{switch(A[i]) {case‘I’: j++; break; //入栈次数增1。case‘O’: k++; if(k>j){printf(“序列非法\n”)；exit(0);} } i++; //不论A[i]是‘I’或‘O’，指针i 均后移。} if(j!=k) {printf(“序列非法\n”)；return(false);} else {printf(“序列合法\n”)；return(true);} }//算法结束。 [算法讨论]在入栈出栈序列（即由‘I’和‘O’组成的字符串）的任一位置，入栈次 数（‘I’的个数）都必须大于等于出栈次数（即‘O’的个数），否则视作非法序列，立即 给出信息，退出算法。整个序列（即读到字符数组中字符串的结束标记‘\0’），入栈次数 必须等于出栈次数（题目中要求栈的初态和终态都为空），否则视为非法序列。4．[题目分析]两栈共享向量空间，将两栈栈底设在向量两端，初始时，s1 栈顶指针为-1， s2 栈顶为maxsize。两栈顶指针相邻时为栈满。两栈顶相向，迎面增长，栈顶指针指向栈顶 元素。 #define maxsize 两栈共享顺序存储空间所能达到的最多元素数 #define elemtp int //假设元素类型为整型typedef struct {elemtp stack[maxsize]; //栈空间 int top[2]; //top 为两个栈顶指针 }stk; stk s; //s 是如上定义的结构类型变量，为全局变量。 (1)入栈操作： int push(int i,int x) //入栈操作。i 为栈号，i=0 表示左边的栈s1，i=1表示右边的栈s2，x是入栈元素。 入栈成功返回1，否则返回0。 {if(i<0||i>1){printf(“栈号输入不对”);exit(0);} if(s.top[1]-s.top[0]==1) {printf(“栈已满 \n”);return(0);} switch(i) {case 0: s.stack[++s.top[0]]=x; return(1); break; case 1: s.stack[--s.top[1]]=x; return(1); } }//push （2）退栈操作 elemtp pop(int i) //退栈算法。i 代表栈号，i=0 时为s1栈，i=1 时为s2 栈。退栈成功返回退栈元素， 否则返回-1。 {if(i<0 || i>1){printf(“栈号输入错误\n”)；exit(0);} switch(i) {case 0: if(s.top[0]==-1) {printf(“栈空\n”)；return（-1）；} else return(s.stack[s.top[0]--]); case 1: if(s.top[1]==maxsize {printf(“栈空\n”); return(-1);} else return(s.stack[s.top[1]++]); } }//算法结束 [算法讨论] 请注意算法中两栈入栈和退栈 时的栈顶指针的计算。两栈共享空间示意图略，s1 栈是通常意义下的栈，而s2 栈入栈操作时，其栈顶指针左移（减1），退栈时，栈顶 指针右移（加1）。 5. [题目分析]栈的特点是后进先出，队列的特点是先进先出。所以，用两个栈s1 和s2 模 拟一个队列时，s1 作输入栈，逐个元素压栈，以此模拟队列元素的入队。当需要出队时， 将栈s1 退栈并逐个压入栈s2中，s1 中最先入栈的元素，在s2 中处于栈顶。s2 退栈，相当 于队列的出队，实现了先进先出。显然，只有栈s2为空且s1 也为空，才算是队列空。 (1) int enqueue(stack s1,elemtp x) //s1 是容量为n 的栈，栈中元素类型是elemtp。本算法将x 入栈，若入栈成功返回1， 否则返回0。 {if(top1==n && !Sempty(s2)) //top1 是栈s1 的栈顶指针，是全局变量。 {printf(“栈满”);return(0);} //s1 满s2 非空,这时s1 不能再入栈。 if(top1==n && Sempty(s2)) //若s2为空，先将s1 退栈,元素再压栈到s2。 {while(!Sempty(s1)) {POP(s1,x);PUSH(s2,x);} PUSH(s1,x); return(1); //x 入栈，实现了队列元素的入队。 } (2) void dequeue(stack s2,s1) //s2 是输出栈，本算法将s2栈顶元素退栈，实现队列元素的出队。 {if(!Sempty(s2)) //栈s2 不空，则直接出队。{POP(s2,x); printf(“出队元素为”,x); } else //处理s2 空栈。 if(Sempty(s1)) {printf(“队列空”);exit(0);}//若输入栈也为空，则判 定队空。 else //先将栈s1 倒入s2 中，再作出队操作。{while(!Sempty(s1)) {POP(s1,x);PUSH(s2,x);} POP(s2,x); //s2 退栈相当队列出队。 printf(“出队元素”，x); } }//结束算法dequue。 (3) int queue_empty() //本算法判用栈s1和s2 模拟的队列是否为空。 {if(Sempty(s1)&&Sempty(s2)) return(1);// 队列空。 else return(0); //队列不空。 } [算法讨论]算法中假定栈s1 和栈s2 容量相同。出队从栈s2 出，当s2 为空时，若s1 不空，则将s1 倒入s2 再出栈。入队在s1，当s1满后，若s2空，则将s1 倒入s2，之后再 入队。因此队列的容量为两栈容量之和。元素从栈s1 倒入s2，必须在s2 空的情况下才能 进行，即在要求出队操作时，若s2空，则不论s1 元素多少（只要不空），就要全部倒入s2 中。 6．【解答】入队算法： int EnterQueue(SeqQueue *Q, QueueElementType x) { /*将元素x 入队*/ if(Q->front==Q->front && tag==1) /*队满*/ return(FALSE); if(Q->front==Q->front && tag==0) /*x 入队前队空，x入队后重新设置标志 */ tag=1; Q->elememt[Q->rear]=x; Q->rear=(Q->rear+1)%MAXSIZE; /*设置 队尾指针*/ Return(TRUE); } 出队算法： int DeleteQueue( SeqQueue *Q , QueueElementType *x) { /*删除队头元素，用x 返回其值*/ if(Q->front==Q->rear && tag==0) /*队空*/ return(FALSE); *x=Q->element[Q->front]; Q->front=(Q->front+1)%MAXSIZE; /*重新设置队头指针*/ if(Q->front==Q->rear) tag=0; /*队头元素出队后队列为空，重新设置标志域 */ Return(TUUE); } 7. [题目分析] 根据队列先进先出和栈后进先出的性质，先将非空队列中的元素出队，并压 入初始为空的栈中。这时栈顶元素是队列中最后出队的元素。然后将栈中元素出栈，依次插 入到初始为空的队列中。栈中第一个退栈的元素成为队列中第一个元素，最后退栈的元素（出 队时第一个元素）成了最后入队的元素，从而实现了原队列的逆置。 void Invert(queue Q) //Q 是一个非空队列，本算法利用空栈S 和已给的几个栈和队列的ADT 函数，将队列Q 中 的元素逆置。 {makempty(S); //置空栈 while (!isEmpty(Q)) // 队列Q 中元素出队{value=deQueue(Q); push(S,value); }// 将出队元素压入栈中 while(!isEmpty(S)) //栈中元素退栈 {value=pop(S); enQueue(Q,value); }//将出栈元素入队列Q }//算法invert 结束 第四章串一、单项选择题 1．B 2. B 3．B 4．C 5. C 二、填空题 1．空、字符 2．由空格字符（ASCII 值32）所组成的字符串空格个数 3．长度、相等、子、主 4．5 5．01122312 6．（1）char s[ ] (2) j++ (3) i >= j 7．[题目分析]本题算法采用顺序存储结构求串s 和串t 的最大公共子串。串s 用i 指针（1<=i<=s.len）。t 串用j 指针 （1<=j<=t.len）。算法思想是对每个i （1<=i<=s.len，即程 序中第一个WHILE 循环），来求从i开始的连续字符串与从j（1<=j<=t.len，即程序中第二 个ＷHILE 循环）开始的连续字符串的最大匹配。程序中第三个（即最内层）的WHILE 循环， 是当s 中某字符（s［i］）与t 中某字符（t ［j］）相等时，求出局部公共子串。若该子串长 度大于已求出的最长公共子串（初始为０），则最长公共子串的长度要修改。 (1) i+k<=s.len && j+k<=t.len && s[i+k]==t[j+k] //所有注释同上（a） (2) con=0 (3) j+=k (4) j++ (5) i++ 三、应用题 1．空格是一个字符，其ASCII 码值是32。空格串是由空格组成的串，其长度等于空格的个 数。空串是不含任何字符的串，即空串的长度是零。 2．(a)A+B “mule” (b)B+A “mule ” (c)D+C+B “myoldmule” (d)SUBSTR(B,3,2) “le” (e)SUBSTR(C,1,0) “” (f)LENGTH(A) 2 (g)LENGTH(D) 2 (h)INDEX(B,D) 0 (i)INDEX(C,”d”) 3 (j)INSERT(D,2,C) “myold” (k)INSERT(B,1,A) “m ule” (l)DELETE(B,2,2) “me” (m)DELETE(B,2,0) “mule” 3．朴素的模式匹配（Brute－Force）时间复杂度是Ｏ（m＊n），KMP算法有一定改进，时间 复杂度达到Ｏ（m＋n）。本题也可采用从后面匹配的方法，即从右向左扫描，比较６次成功。 另一种匹配方式是从左往右扫描，但是先比较模式串的最后一个字符，若不等，则模式串后 移；若相等，再比较模式串的第一个字符，若第一个字符也相等，则从模式串的第二个字符 开始，向右比较，直至相等或失败。若失败，模式串后移，再重复以上过程。按这种方法，本题比较18次成功。 4．next 和nextval值分别为0112123422 和010*******。 5．题中所给操作的含义如下： //：连接函数，将两个串连接成一个串substr（s,i,j）：取子串函数，从串s的第i 个字符开始，取连续j 个字符形成子串replace（s1,i,j,s2）：置换函数，用s2串替换s1串中从第i个字符开始的连续j 个 字符 本题有多种解法，下面是其中的一种：（1）s1=substr（s,3,1）//取出字符：‘y’（2）s2=substr（s,6,1）//取出字符：‘+’（3）s3=substr（s,1,5）//取出子串： ‘(xyz)’ （4）s4=substr（s,7,1）//取出字符：‘*’（5）s5=replace（s3,3,1,s2）//形成部分串：‘（x+z）’ （6）s=s5//s4//s1 //形成串t 即‘（x+z）*y’ 四、算法设计题 1．const maxlen=串的最大长度; typedef struct {char ch [maxlen]; int curlen; } string; int EQUAL_string(string s,string t ) { if (s.curlen!=t.curlen) return(0); for (t=0; t if (s.ch[t]!=t.ch[t] ) return(0); return(1); } 2．设单链表无头结点 const nodesize =用户定义的结点大小；typedef struct node *pointer; struct node {char ch; pointer next; } typedef pointer strlist; int EQULA_strlist(strlist s ,strlist t ) { while ((s!= null )&&(t!=null)&&(s->ch==t->ch)) {s=s->next;t=t->next;} return((t= = null)&&(s= =null)); } 3．分析：首先判断串T 是否为串S 的子串，若串T是串S 的子串对S 中该子串逆置。Int NZ_strlist (strlist s,strlist t) {p=s->next;t=t->next;q=s; while(p!=null) {pp =p ; tt =t; /*判断串T 是否为串S 的子串*/ while ((tt!=null)&&(pp!=null)&&(pp->ch= =tt->ch)) {pp=pp->next;tt=tt->next;} if (tt==null) /*串T 是串S的子串对S 中的该子串的位置*/ {qq=q->next; /* q是子串的第一个结点前趋pp 是子串最后一个结点后继*/ while(qq!=pp) {g=qq; qq= qq->next; q->next =pp; pp=g; } q->next=pp; /*将该子串的前趋与逆置后的子串的相连*/ return(1);/*找到并逆置返1 */ }else {q=p;p=p->next;} } return(0);/*找不到匹配的串返0*/ } 4．[题目分析]设以字符数组s 表示串，重复子串的含义是由一个或多个连续相等的字 符组 成的子串，其长度用max 表示，初始长度为0，将每个局部重复子串的长度与max相比，若 比max 大，则需要更新max，并用index 记住其开始位置。 int LongestString(char s[],int n) //串用一维数组s 存储，长度为n，本算法求最长重复子串，返回其长度。 {int index=0,max=0; //index 记最长的串在s 串中的开始位置，max 记其长度 int length=1,i=0,start=0; //length 记局部重复子串长度，i 为字符数组下标 while(i if(s[i]==s[i+1]) {i++; length++;} else //上一个重复子串结束 {if(max 更新max i++;start=i;length=1; //初始化下一重复子串的起始 位置和长度 } printf(“最长重复子串的长度为%d，在串中的位置%d\n”，max,index); return(max); }//算法结束 [算法讨论]算法中用i 即最后一个字符。子串长度的初值数为1，表示一个字符自然等于其身。 算法的时间复杂度为O(n)，每个字符与其后继比较一次。 5．[题目分析]实现字符串的逆置并不难，但本题“要求不另设串存储空间”来实现字符串 逆序存储，即第一个输入的字符最后存储，最后输入的字符先存储，使用递归可容易做到。 void InvertStore(char A[]) //字符串逆序存储的递归算法。 { char ch; static int i = 0;//需要使用静态变量 scanf ("%c",&ch); if (ch!= '.') //规定'.'是字符串输入结束标志{InvertStore(A); A[i++] = ch;//字符串逆序存储 } A[i] = '\0'; //字符串结尾标记 }//结束算法InvertStore。 第5 章数组和广义表 一、单项选择题 1．C 2．C 3．A 4．A 5．B 6．A 7．C 8．C 9．C 10．C 11．A 二、填空题 1．顺序、列序、行序 2. 第1 行第3 列 3．i(i-1)/2+j (1<=i,j<=n) 4. 非零元很少(t< 本质就是广义表，因作为广义表的元素故称为子表。 （2）大写字母（3）小写字母（4）表中元素的个数（5）表展开后所含括号的层数6．（1）（）（2）（（））（3）2 （4）2 7．col<=a.nu, a.data[p].j, q++ 8. （1）(p->tag==0) //处理原子 （2）h=reverse(p->val.ptr.hp) //处理表头（3）(p->val.ptr.tp) //产生表尾的逆置广义表 （4）s->val.ptr.tp=t; //连接 （5）q->val.ptr.hp=h //头结点指向广义表 三、应用题 1. 958 三维数组以行为主序存储，其元素地址公式为： LOC(A ijk)=LOC(A c1c2c3)+[(i-c1)V2V3+(j-c2)V3+ (k-c3)]*L+1 其中c i,d i是各维的下界和上界，V i=d i-c i+1是各维元素个数，L 是一个元素所占的存储单元数。 2. 特殊矩阵指值相同的元素或零元素在矩阵中的分布有一定规律，因此可以对非零元素分 配单元（对值相同元素只分配一个单元），将非零元素存储在向量中，元素的下标i 和j 和 该元素在向量中的下标有一定规律，可以用简单公式表示，仍具有随机存取功能。而稀疏矩 阵是指非零元素和矩阵容量相比很小 （t< 自然失去了随机存取的功能。即使用三元组表的顺序存储结构，存取下标为i 和j 的元素时， 要扫描三元组表，下标不同的元素，存取时间也不同，最好情况下存取时间为O(1)，最差 情况下是O(n)，因此也失去了随机存取的功能。 3. 数组是具有相同性质的数据元素的集合，同时每个元素又有唯一下标限定，可以说数组 是值和下标偶对的有限集合。n维数组中的的 计算机公共基础教学大纲 Final approval draft on November 22, 2020 《计算机公共基础》课程教学大纲课程名称：计算机公共基础 授课对象：计算机应用类专业 计算机公共基础是一门实践性很强的课程，本课程的教学内容是在对真实工作任务进行分析研究的基础上，进行知识和技能的整合、序化后形成教学项目，采用“项目引导、任务驱动”的教学模式，以项目为载体开展教学活动，指导学生体验职业活动情境，培养其职业素养。 一、教学目标设计 1、知识目标 （1）了解计算机的基本概念、熟悉计算机的组成，学会操作系统的安装。 （2）了解计算机网络的概念，掌握Internet的应用。 （3）了解操作系统的基本概念，掌握WindowsXP的常用操作。（4）了解Word2003的基本知识，掌握其操作方法。 （5）了解Excel2003的基本概念和功能，掌握数据处理和图表制作的基本方法。 （6）掌握PowerPoint2003制作演示文稿的基本方法。 （7）了解数据库的基本概念，掌握CDT各模块功能。 2、能力目标 （1）能按用户需求选购性价比高的计算机。 （2）具备浏览网页、收发电子邮件、下载资料等能力。 （3）能熟练操作WindowsXP，并会设置系统环境。 （4）能使用Word2003进行文字、图表的编排。 （5）能使用Excel2003进行数据处理，创建图表。 （6）能使用PowerPoint2003制作演示文稿。 （7）能使用CDT各核心模块，开发简单信息管理系统。 3、素质目标 （1）培养学生认真分析解决问题的能力。 （2）使用网络资源的能力。 （3）培养学生细致而耐心的工作能力。 （4）培养学生的发散性思维。 （5）培养学生综合运用知识的能力。 （6）培养学生的审美情趣。 （7）培养学生独立思考和创新能力。 （8）培养学生沟通与表达能力。 （9）培养学生职业道德。 （10）培养学生团队协作能力。 （11）培养学生阅读理解能力。 二、教学内容设计 项目一选购计算机 一、项目综述 1、项目背景 某学校通过政府采购方式购置一批办公用计算机，按标书提供的，进行计算机选型，为投标提供依据。 2、项目实现目标 按用户要求进行计算机选型；安装操作系统。 第1 页 共8页 第2 页 共8页 中等职业学校公共基础课水平测试 计算机应用基础测试试卷B （满分：100分;时间：90分钟) 1. 在Word 中，如果想为文档插入页眉页脚，则选择下列那个菜单。 ( ) A ．文件 B ．格式 C ．编辑 D ．插入 2.因特网是属于 所有。 （ ） A ．中国政府 B ．微软公司 C ．各接入单位共同 D ．美国政府 3扩展名为.MOV 的文件通常是一个（ ） A ．音频文件 B ．视频文件 C ．图片文件 D ．文本文件 4. 以下软件中，（ ）不是操作系统软件。 （ ） A ．Windows xp B ．unix C ．linux D ．Microsoft office 5. 不属于Microsoft Office 软件包的软件是______。 A ．Mail B ．Excel C ．Windows D ．word 6．下列设备中不是计算机网络专用设备的是。 ( ) A ．集线器 B ．电话机 C ．交换机 D ．网卡 7．在编辑演示文稿时，要在幻灯片中插入表格、剪贴画或照片等图形，应在____中进行。 A ．备注页视图 B ．幻灯片浏览视图 C ．幻灯片窗格 D ．大纲窗格 8．CPU 主要由运算器和( )组成 A ．控制器 B ．存储器 C ．寄存器 D ．编辑器 9．在Windows 中，“任务栏” ( ) ( ) A ．只能改变位置不能改变大小 B ．只能改变大小不能改变位置 C ．即不改变位置也不能改变大小 D ．既能改变位置也能改变大小 10．在excel 中，工作表中输入公式，以（）字符开始。 A ．+ B ．＝ C ．？ D ．$ 11．SMTP 是一个基于_____的协议，它是Internet 上传输_______的标准。 A ．多媒体 Web 数据 B ．文本 Web 数据 C ．多媒体 邮件 D ．文本 邮件 12．在Windows 中, 下列叙述错误的是（）。 A ．对文件执行复制操作后，该文件可被粘贴多次。 B ．对文件执行复制操作后，“剪贴板”中存放该文件存放的路径。 C ．对文件执行剪切操作后，该文件可被粘贴多次。 D ．对文件执行复制操作后，该文件可被粘贴一次。 13．以下四项不属于Windows 操作系统特点的是（ ）。 A ．不会受到黑客攻击 B ．即插即用 C ．多任务 D ．图形界面 14．在Windows 中，按Print Screen 键，则整个屏幕的内容（ ） A ．复制到剪贴板 B ．复制到指定文件 C ．打印到指定文件 D ．打印到纸上 15．在控制面板中，使用"添加/删除程序"的作用是( )。 A ．设置字体 B ．设置显示属性 C ．安装未知新设备 D ．安装卸载程序 16．在智能ABC 汉字输入法状态下按（）可以在全角/半角之间切换。 A ．Shift + Space B ．Shift + Ctrl C ．Shift + Alt D ．Shift +Esc 17．计算机断电后，会使存储的数据丢失的存储器是。 （ ） A ．RAM B ．硬盘 C ．ROM D ．软盘 一、单项选择题（每小题1分,共50分） 学校______________________姓名:______________学号:_________________年级:______________ 专业:_____________ …….…………………………….密…………………………………封…………………………………线…………………………………… (1)下面叙述正确的是______。(C) A. 算法的执行效率与数据的存储结构无关 B. 算法的空间复杂度是指算法程序中指令（或语句）的条数（指的是算法所占用的空间） C. 算法的有穷性是指算法必须能在执行有限个步骤之后终止 D. 以上三种描述都不对 (2) 以下数据结构中不属于线性数据结构的是______。(C) A. 队列 B. 线性表 C. 二叉树 D. 栈 (3) 在一棵二叉树上第5层的结点数最多是______。(B)2n-1 A. 8 B.16 C. 32 D. 15 (4) 下面描述中，符合结构化程序设计风格的是______。(A) A. 使用顺序、选择和重复（循环）三种基本控制结构表示程序的控制逻辑 B. 模块只有一个入口，可以有多个出口(可以有0个入口) C. 注重提高程序的执行效率 D. 不使用goto语句（只是限制使用） (5) 下面概念中，不属于面向对象方法的是______。(D) A. 对象 B. 继承 C. 类 D. 过程调用 (6) 在结构化方法中，用数据流程图（DFD）作为描述工具的软件开发阶段是______。 (B) A. 可行性分析 B. 需求分析 C. 详细设计 D. 程序编码 (7) 在软件开发中，下面任务不属于设计阶段的是______。(D) A. 数据结构设计 B. 给出系统模块结构 C. 定义模块算法 D. 定义需求并建立系统模型(8) 数据库系统的核心是______。(B) A. 数据模型 B.数据库管理系统 C. 软件工具 D. 数据库 (9) 下列叙述中正确的是______。(C) A. 数据库是一个独立的系统，不需要操作系统的支持 B. 数据库设计是指设计数据库管理系统 C.数据库技术的根本目标是要解决数据共享的问题 第一章数据结构 一、选择题 （1）下列数据结构中，能用二分法进行查找的是 A）顺序存储的有序线性表 B）线性链表 C）二叉链表 D）有序线性链表 【答案】A 【解析】二分查找只适用于顺序存储的有序表。在此所说的有序表是指线性表中的元素按值非递减排列(即从小到大．但允许相邻元素值相等)的。选项A正确。 （2）下列关于栈的描述正确的是 A）在栈中只能插入元素而不能删除元素 B）在栈中只能删除元素而不能插入元素 C）栈是特殊的线性表，只能在一端插入或删除元素 D）栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素 【答案】C 【解析】栈是一种特殊的线性表，其插入与删除运算都只在线性表的一端进行。由此可见，选项A、选项B和选项D错误，正确答案是选项C。 （3）下列叙述中正确的是 A）一个逻辑数据结构只能有一种存储结构 B）数据的逻辑结构属于线性结构，存储结构属于非线性结构 C）一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率 D）一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率 【答案】D 【解析】一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、索引等存储结构。而采用不同的存储结构，其数据处理的效率是不同的。由此可见，选项D的说法正确。 (4)算法执行过程中所需要的存储空间称为算法的 A）时间复杂度B）计算工作量C）空间复杂度D）工作空间 【答案】c 【解析】算法执行时所需要的存储空间，包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间，其中额外空间还包括算法程序执行过程的工作单元以及某种数据结构所需要的附加存储空间。这些存储空间共称为算法的空间复杂度。 (5)下列关于队列的叙述中正确的是 A）在队列中只能插入数据B）在队列中只能删除数据 C）队列是先进先出的线性表D）队列是先进后出的线性表 【答案】c 【解析】对队列可以进行插入和删除数据的操作，只是插入数据只能在队尾，删除数据只能在队头。所以队列是先进先出的线性表。 (6)设有下列二叉树： A 计算机公共基础知识 一、选择题 1、世 2、计 3、世 4、计 5、电但至今其运行仍遵循着一位科学家提出的基本原理。他就 6、1946_ 7、在 8、 9、计 10、 11、计算机业界最初的硬件巨头“蓝色巨人”指的是 12、第四媒体是指（网络媒体）。 13、CAD A、计算机辅助教育 B、计算机辅助测试 C、计算机辅助设计 D、计算机辅助管理 14、“计算机辅助制造”的英文缩写为CAM。Assist 辅助 15、 16、 17、某单位自行开发的工资管理系统，按计算机应用的类型划分，它属于____。 A、科学计算 B、辅助设计 C、数据处理D 18、 19、 20、 21、 22、 23、在微机中，bit 24、计算机中字节是常用单位，它的英文名字是 Ａ、Bit B、byte C、bout D、baut 25、计算机存储和处理数据的基本单位是____。 A、bit B、Byte C、GB D、KB 26、1字节表示____位。 A、1 B、4 C、8 27、在描述信息传输中bps 28、"32位微型计算机"中的32 29、 30、字符串“IBM”中的字母B存放在计算机内占用的二进制位个数是____。 A、8 B、4 C、2 D、1 31、若一台计算机的字长为4 32、 33、 34、 35、 A、调制解调器 B、交换机C 36、计算机的三类总线中，不包括____。 A、控制总线 B、地址总线 C、传输总线 D、数据总线 37、关于计算机总线的说明不正确的是____。 A、计算机的五大部件通过总线连接形成一个整体 B、总线是计算机各个部件之间进行信息传递的一组公共通道 40、 41、几年前一位芬兰大学生人在Internet 上公开发布了一种免费操作系统经过许多人的努力，该 42、Access 43、 44、 45、 46、启动Windows 47、Windows 48、在Windows 49、对于Windows，下面以____为扩展名的文件是不能运行的。 A、.COM B、.EXE C、.BA T D、.TXT 50、在Windows 中有两个管理系统资源的程序组，它们是____。 A、“我的电脑”和“控制面板” B、“资源管理器”和“控制面板” C、“我的电脑”和“资源管理器” D、“控制面板”和“开始”菜单 51、在Windows中，为了查找文件名以"A" 52、中，为了查找文件名以"A"字母打头，后跟一字母的所有文件，应当在查找名称框内输 53、 54、合键 55、Word程序启动后就自动打开一个名为____的文档。 A、Noname B、Untitled C、文件1 D、文档1 56、Word程序允许打开多个文档，用____菜单可以实现各文档窗口之间的切换。 A、编辑 B、窗口 C、视图 D、工具 57、下列带有通配符的文件名，能表示文件ABC、TXT的是____。 A、*BC、? B、A?.* C、?BC、* D、?.? 58、为了保证任务栏任何时候在屏幕上可见，应在"任务栏属性"对话框的"任务栏选项"标签中选择____。Ａ、不被覆盖B、总在最前C、自动隐藏D、显示时钟 59、使用“开始”菜单中的查找命令，要查找的文件名中可以使用____。 A、通配符? B、通配符* C、两者都可以 D、两者都不可以 60、Windows xp中，当屏幕上有多个窗口时，那么活动窗口____。 A、可以有多个窗口 B、只能是固定的窗口 C、是没有被其他窗口盖住的窗口 D、是有一个标题栏颜色与众不同的窗口 61、WINDOWS资源管理器中，反向选择若干文件的方法是____。 A、CTRL+单击选定需要的文件 B、SHIFT+单击选定需要的文件，再单击反向选择 C、用鼠标直接单击选择 D、CTRL+单击选定不需要的文件，再单击编辑菜单中反向选择 62、对WINDOWS应用程序窗口快速重新排列[平铺或层叠]的方法是: ____。 A、可通过工具栏按钮实现 B、可通过任务栏快捷菜单实现 C、可用鼠标调整和拖动窗口实现 D、可通过[开始]菜单下的[设置]命令实现 63、通常把计算机网络定义为____。 A、以共享资源为目标的计算机系统，称为计算机网络 B、能按网络协议实现通信的计算机系统，称为计算机网络 C、把分布在不同地点的多台计算机互联起来构成的计算机系统，称为计算机网络 计算机二级公共基础知识重点讲解汇总 章节名称内容简介 第一章数据结构与算法本章主要介绍算法的基本概念、数据结构的 定义、线性表、树等重点知识的讲解。 第二章程序设计基础本章主要介绍程序设计风格、结构化程序设 计、面向对象程序设计等重点知识的讲解。 第三章软件工程基础本章主要介绍软件工程的基本概念、结构化 分析方法、软件设计等重点知识的讲解。 第四章数据库设计基础本章主要介绍数据库、数据库管理系统 （DBMS）、数据库系统、数据模型、关系运算、 专门关系运算、数据库设计步骤等重点知识的讲 解。 第一章数据机构与算法 数据结构与算法 ◆算法的基本概念 1. 算法：是对问题处理方案的正确而完整的描述，是求解问题的方法，是指令的有效序列。 2. 具有5个特性： （1）有穷性（在有穷步后完成）算法程序的运行时间是有限的 （2）确定性（每一步都有确定的含义） （3）可行性 （4）输入（一个算法有零个或多个输入） （5）输出（一个算法有一个或多个输出） 3. 算法的复杂度 包括：时间复杂度和空间复杂度。二者没有必然的联系。 时间复杂度：执行算法所需要的计算工作量或基本运算次数。 空间复杂度：算法所需要的空间的度量。 ◆数据结构的定义 1. 数据结构包括数据的逻辑结构、数据的存储结构、数据的操作 数据的逻辑结构：数据的外部结构，指各数据元素之间的逻辑关系，反映人们对数据含义的解释。包括：线性结构（线性表、栈、队列）和非线性结构（树和图） 数据的存储结构：数据的物理结构，指数据的逻辑结构在计算机中的表示。 一个逻辑结构可以有多种存储结构。 ◆线性表：线性表中元素的个数n（n>=0）定义为线性表的长度。 顺序存储是线性表的一种最常用的存储方式。 线性表的顺序存储结构和线性表的链式存储结构分别是随机存取的存储结构和顺序存取的存储结构。 1.栈：是限定在表尾进行插入和删除操作的线性表。具有记忆功能只能顺序存储（错） 允许插入和删除的一端叫栈顶。另一端叫栈底。 后进先出的线性表 2队列：是限定在一端插入而在另一端删除，插入端叫队尾，删除端叫对头。 先进先出的线性表 3栈和队列的顺序存储结构 循环队列属于线性表存储结构中顺序存储结构和链式存储结构的前者。 ◆树 1.定义:树的结点、度（结点的度）、叶子（终端结点）、数的度、深度、有序树和无序数 2.二叉树：结点至多有两棵子树，并且二叉树的子树有之分，次序不能颠倒。 性质：★在二叉树的第i层上至多有2i-1个结点 ★深度为k的二叉树至多有2k-1个结点。 ★对任一个二叉树T，如果其叶子（终端结点数）为n，度为二的结点数为m,则n=m +1. ★具有n个结点的完全二叉树的深度为k+1，其中k是㏒2n的整数部分。 2. 二叉树的遍历 ▼先序遍历（根—左—右） ▼中序遍历（左—根—右） ▼后序遍历（左—右—根） ◆查找算法 （1）顺序查找 顺序查找的平均查找长度为（n+1）／2，最坏的情况下比较的次数为n (2) 二分查找 限定于顺序存储的有序线性表 ◆排序算法 （1）插入类排序 ▲直接插入排序 ▲折半插入排序 ▲希尔排序 （2）交换类排序 计算机公共基础部分知识归纳 第一章数据结构与算法 算法---是一组严谨地定义运算顺序的规则 算法的基本要素---一是对数据对象的运算和操作，二是算法的控制结构 算法设计基本方法---列举法、归纳法、递推、递归、减半递推 算法的复杂度---包括时间复杂度和空间复杂度 时间复杂度---执行算法所需的计算工作量 空间复杂度---执行算法所需的内存空间 数据结构---相互有关联的数据元素的集合。如春、夏、秋、冬；18、11、35、23、16。。。； 父亲、儿子、女儿等都是数据元素。 前件---数据元素之间的关系，如父亲是儿子和女儿的前件 后件---如儿子是父亲的后件 结构---指数据元素之间的前后件关系 数据的逻辑结构—是指反映数据元素之间逻辑关系，而与它们在计算机中的存储位置无关数据的存储结构（物理结构）---数据的逻辑结构在计算机存储空间中的存放形式，数据元素 在计算机存储空间的位置关系可能与逻辑关系不同。 根据数据结构中各数据元素之间前后件关系的复杂程度，可将数据结构分两类---线性结构与 非线性结构 线性结构（线性表）---满足下列两个条件（1）有且只有一个根结点（2）每一个结点最多有 一个前件和后件。则称该数据结构为线性结构，否则为非线 性结构。 线性表是最简单、最常用的一种数据结构，其数据元素之间的相对位置是线性的，其存储方 式为顺序存储的，如数组 栈---是限定在一端进行插入与删除的线性表，一端封闭，另一端开口，其操作原则是“先进 后出”，栈的运算有入栈、退栈、读栈顶元素 队列---是指在一端进行插入（称为队尾）而在另一端进行删除（称为队头）的线性表，其操 作规则是“先进先出”，其运算有入队和退队。 树---是一种简单的非线性结构，而且是层次结构，是倒立的大树，有根结点、父结点、子结 点、叶子结点。根结点在第一层，一个结点所拥有的后件的 个数称为该结点的度，所有结点中最大的度称为树的度， 树的最大层次称为树的深度。 二叉树---（1）非空二叉树只有一个根结点（2）每一个结点最多有两棵子树（左子树和右子 树），其存储结构为链式。 二叉树性质---（1）K层上最多有2（K-1）个结点（2）深度为m的二叉树最多有2m-1个结点（3）度为0的结点（叶子结点）比度为2的结点多一个（4）具有n个结点的 二叉树，其深度至少为[Log2n]+1，其中[Log2n]表示对Log2n 取整 满二叉树---除最后一层外，其余层的结点都有两个子结点 完全二叉树---除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的 若干结点，叶子结点只可能在层次最大的两层上出现。满二 叉树是完全二叉树，而完全二叉树不是满二叉树。完全二叉 树有两个性质：（1）具有n个结点的完全二叉树的深度为 [Log2n]+1（2） 龙源期刊网 https://www.doczj.com/doc/962626537.html, 高校计算机公共基础课实验报告改革探讨 作者：李倩 来源：《计算机光盘软件与应用》2013年第05期 摘要：实验报告在高校计算机公共基础课实验教学中发挥着重要的作用。首先分析了当前实验报告存在的问题，然后针对这些问题从实验预习、实验报告模板设计、实验报告提交时间、实验报告批改规范以及采用电子实验报告进行现代化管理等方面提出了一系列的改进措施，最后对实验报告的发展趋势进行了展望。 关键词：实验报告；实验教学；实验预习；实验报告模板；电子实验报告 中图分类号：TP3-4 文献标识码：A文章编号：1007-9599 （2013） 05-0000-02 1引言 近年来，高校对计算机公共基础课实验教学的重视程度逐步提升，实验报告成为检查考核实验教学质量的重要依据之一。书写实验报告是实验教学中的一个非常重要的环节。通过书写实验报告，对实验过程和结果进行分析总结，不但能使学生将理论和实验进一步联系起来，更好地掌握知识和技能，同时也为学生今后从事科研、撰写毕业论文奠定了一定的基础。然而，在实验报告日益被重视的同时，在其使用过程中逐渐暴露出了一些问题，严重影响着实验教学质量的提高。 2实验报告存在的主要问题 高校计算机公共基础课一般都要求学生在实验结束后填写并提交实验报告，教师对实验报告进行批改，课程结束后对实验报告进行归档，通过对实验报告的检查来检验评价实验教学的质量。其中，存在着一些问题，主要有以下几个方面：2.1实验报告与实验过程脱节。通常，学生在实验课上完成实验操作，在课后书写实验报告。学生填写实验报告时往往要努力回想课上实验的情形，然而由于时间上的脱节使得填写的内容不能完全真实地反映实验过程和结果，因而也就不能充分地发挥实验报告的作用。2.2纸质实验报告存在诸多缺点。传统纸质实验报告已经不能满足当前实验教学的要求，且逐渐暴露出诸多弊端。首先，纸质实验报告的填写、批改和反馈整个过程会花费很多的时间。实验报告批改和反馈效率低，学生也就不能及时获得教师评价，了解需改进之处，从而降低了实验教学的效果。其次，纸质实验报告在填写内容上会有局限，如对于一些较复杂的图形形式的实验结果不易表现，且篇幅有限。再次，纸质形式不便于查阅往届实验报告，不便于对学生实验报告的情况进行统计汇总，从而不利于全面评价实验教学效果。总之，纸质实验报告的形式不符合教育现代化、网络化发展的要求，同时，大量纸张的使用造成很大的浪费且存储不便。2.3实验报告抄袭现象严重。目前很多高校都存在这样的现象：学生书写实验报告就是应付了事，随便填填，甚至抄袭，一个班上交上来的实验报告就那么几个版本，实验抄袭现象严重。造成这种现象的原因是多方面的。首先，实验报告 全国计算机二级考试公共基础知识题库 习题一 (1) 在下列选项中，哪个不是一个算法一般应该具有的基本特征______。(C) A. 确定性 B. 可行性 C. 无穷性 D. 拥有足够的情报 (2) 希尔排序法属于哪一种类型的排序法______。(B) A. 交换类排序法 B. 插入类排序法 C. 选择类排序法 D. 建堆排序法 (3) 下列关于队列的叙述中正确的是______。(C) A. 在队列中只能插入数据 B. 在队列中只能删除数据 C. 队列是先进先出的线性表 D. 队列是先进后出的线性表 (4) 对长度为N的线性表进行顺序查找，在最坏情况下所需要的比较次数为______。(B) A. N+1 B. N C.(N+1)/2 D. N/2 (5) 信息隐蔽的概念与下述哪一种概念直接相关______。(B) A. 软件结构定义 B. 模块独立性 C. 模块类型划分 D. 模拟耦合度 (6) 面向对象的设计方法与传统的的面向过程的方法有本质不同，它的基本原理是______。(C) A. 模拟现实世界中不同事物之间的联系 B. 强调模拟现实世界中的算法而不强调概念 C. 使用现实世界的概念抽象地思考问题从而自然地解决问题 D. 鼓励开发者在软件开发的绝大部分中都用实际领域的概念去思考 (7) 在结构化方法中，软件功能分解属于下列软件开发中的阶段是______。(C) A. 详细设计 B. 需求分析 C. 总体设计 D. 编程调试 (8) 软件调试的目的是______。(B) A. 发现错误 B. 改正错误 C. 改善软件的性能 D. 挖掘软件的潜能 (9) 按条件f对关系R进行选择，其关系代数表达式为______。(C) A. R|X|R B. R|X|R C. бf(R) 第一章数据结构与算法 算法 1、算法:是指解题方案的准确而完整的描述。算法不等于程序,也不等计算机方法,程序的编制不可能优于算法的设计。 2、算法的基本特征：是一组严谨地定义运算顺序的规则,每一个规则都是有效的，是明确的,此顺序将在有限的次数下终止。特征包括：（1）可行性;（2)确定性(3）有穷性（4）拥有足够的情报。 ３、算法的基本要素:一是对数据对象的运算和操作；二是算法的控制结构。 ４、指令系统:一个计算机系统能执行的所有指令的集合。 5、基本运算包括:算术运算、逻辑运算、关系运算、数据传输。 ６、算法的控制结构：顺序结构、选择结构、循环结构。 7、算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。 8、算法复杂度:算法时间复杂度和算法空间复杂度。 9、算法时间复杂度是指执行算法所需要的计算工作量。 10、算法空间复杂度是指执行这个算法所需要的内存空间。 数据结构的基本基本概念 1、数据结构研究的三个方面: (1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构; （2）在对数据进行处理时，各数据元素在计算机中的存储关系,即数据的存储结构;（3）对各种数据结构进行的运算。数据结构是指相互有关联的数据元素的集合。 ２、数据的逻辑结构包含:(1）表示数据元素的信息;(2）表示各数据元素之间的前后件关系。数据的存储结构有顺序、链接、索引等。 ３、线性结构条件：(1）有且只有一个根结点;(２）每一个结点最多有一个前件，也最多有一个后件。非线性结构：不满足线性结构条件的数据结构。 线性表及其顺序存储结构 １、线性表是由一组数据元素构成,数据元素的位置只取决于自己的序号,元素之间的相对位置是线性的。在复杂线性表中,由若干项数据元素组成的数据元素称为记录,而由多个记录构成的线性表又称为文件。 2、非空线性表的结构特征: (1）且只有一个根结点ａ1，它无前件；(2)有且只有一个终端结点an，它无后件; （3)除根结点与终端结点外,其他所有结点有且只有一个前件,也有且只有一个后件。结点个数n称为线性表的长度,当ｎ=0时，称为空表。 3、线性表的顺序存储结构具有以下两个基本特点：(１）线性表中所有元素的所占的存储空间是连续的; (2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 4、顺序表的运算:插入、删除。 栈和队列 1、栈是限定在一端进行插入与删除的线性表,允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。栈按照“先进后出”（FILO)或“后进先出”(LＩFO）组织数据,栈具有记忆作用。用ｔop表示栈顶位置，用ｂottoｍ 表示栈底。 2、栈的基本运算：(1）插入元素称为入栈运算；（2)删除元素称为退栈运算;（３）读栈顶元素是将栈顶元素赋给一个指定的变量,此时指针无变化。 3、队列是指允许在一端（队尾）进入插入,而在另一端(队头）进行删除的线性表。Ｒear指针指向队尾,frｏnt 指针指向队头。 4、队列是“先进行出”(FIFO)或“后进后出”(LILO)的线性表。 线性链表 2010年9月全国计算机等级考试公共基础知识试题及答案 一、选择题（每小题2分）下列各题A）、B）、C）、D）四个选项中，只有一个选项是正确的。请将正确选项填涂在答题卡相应位置上，答在试卷上不得分。 （1）下列叙述中正确的是 A）线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的 B）线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构 C）线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构 D）上述三种说法都不对 （2）下列叙述中正确的是 A）在栈中，栈中元素随栈底指针与栈顶指针的变化而动态变化 B）在栈中，栈顶指针不变，栈中元素随栈底指针的变化而动态变化 C）在栈中，栈底指针不变，栈中元素随栈顶指针的变化而动态变化 D）上述三种说法都不对 （3）软件测试的目的是 A）评估软件可靠性B）发现并改正程序中的错误 C）改正程序中的错误D）发现程序中的错误 （4）下面描述中，不属于软件危机表现的是 A）软件过程不规范B）软件开发生产率低 C）软件质量难以控制D）软件成本不断提高 （5）软件生命周期是指 A）软件产品从提出、实现、使用维护到停止使用退役的过程 B）软件从需求分析、设计、实现到测试完成的过程 C）软件的开发过程 D）软件的运行维护过程 （6）面向对象方法中，继承是指 A）一组对象所具有的相似性质B）一个对象具有另一个对象的性质 C）各对象之间的共同性质D）类之间共享属性和操作的机制 （7）层次型、网状型和关系型数据库划分原则是 A）记录长度B）文件的大小 C）联系的复杂程度D）数据之间的联系方式 （8）一个工作人员可以使用多台计算机，而一台计算机可被多个人使用，则实体工作人员、与实体计算机之间的联系是 A）一对一B）一对多C）多对多D）多对一 （9）数据库设计中反映用户对数据要求的模式是 A）内模式B）概念模式C）外模式D）设计模式 （10）有三个关系R、S和T如下： 范文 2020年公共基础知识计算机练习题 1/ 10 2020 年公共基础知识计算机练习题 1[单选题] 一个栈的初始状态为空。 现将元素 1，2，3，A，B，C 依次入栈，然后再依次出栈，则元素出栈的顺序是 A.1，2，3，A，B，C B.C，B，A，1，2，3 C.C，B，A，3，2，1 D.1，2，3，C，B，A 参考答案：C 参考解析：栈的修改是按后进先出的原则进行的，所以顺序应与入栈顺序相反，故选 c。 2[单选题] 数据字典(DD)所定义的对象都包含于 A.数据流图(DFD 图)B.程序流程图 C.软件结构图 D.方框图 参考答案：A 参考解析：在数据流图中，对所有元素都进行了命名，所有名字的定义集中起来就构成了数据字典。 因此选 A，而 B、C、D 都不符合。 3[单选题] 下面属于白盒测试方法的是 A.等价类划分法 B.逻辑覆盖 C.边界值分析法 D.错误推测法参考答案：B 参考解析：白盒测试法主要有逻辑覆盖、基本路径测试等。 逻辑覆盖测试包括语句覆盖、路径覆盖、判定覆盖、条件覆盖、判断一条件覆盖，选择 B。 其余为黑盒测试法。 5[单选题] 下列关于栈的叙述中，正确的是 A.栈底元素一定是最后入栈的元素 B.栈顶元素一定是最先入栈的元素 C.栈操作遵循先进后出的原则 D.以上说法均错误参考答案：C 3/ 10 参考解析：栈顶元素总是后被插入的元素，从而也是最先被删除的元素;栈底元素总是最先被插入的元素，从而也是最后才能被删除的元素。 栈的修改是按后进先出的原则进行的。 因此，栈称为先进后出表，或“后进先出”表，所以选择 C。 6[单选题] 下列叙述中正确的是 A.循环队列中的元素个数随队头指针与队尾指针的变化而动态变化 B.循环队列中的元素个数随队头指针的变化而动态变化 C.循环队列中的元素个数随队尾指针的变化而动态变化 D.以上说法都不对参考答案：A 参考解析：在循环队列中，用队尾指针 rear 指向队列中的队尾元素，用排头指针front 指向排头元素的前一个位置。 因此，从排头指针 front 指向的后一个位置直到队尾指针 rear 指向的位置之间所有的元素均为队列中的元素。 所以循环队列中的元素个数与队头指针和队 计算机二级公共基础知识要点总结 1.栈按先进后出的原则组织数据，所以入栈最早的最后出栈，而队列是先进先出的线性 表。 2.循环队列有队头和队尾两个指针，但是循环队列仍是线性结构的线性表。 在循环队列中只需要对头指针与队尾两个指针来共同反映队列中元素的动态变化情况。 3.当有序线性表为顺序存储时才能用二分法查找。可以证明的是对于长度为n的有序线性 表，在最坏的情况下二分法查找只需要比较log2n次，而顺序查找需要比较n次。 4.链式存储结构既可以针对线性结构也可以针对非线性结构。 链式存储结构中每个结点都由数据域与指针域两部分组成，增加了存储空间。 顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的。 5.数据流图中带箭头的线段表示的是数据流，即沿箭头方向传送数据的通道一般在旁边标 注数据流名。 程序流程图中带有箭头的线段表示的是控制流。 6.在软件开发中，需求分析阶段可以使用的工具有数据流图DFD图，数据字典DD，判定 树与判定表。 7.“对象”有如下一些基本特点：标识唯一性，分类型，多态性，封装性，模块独立性好。 8.数据管理发展至今已经历了三个阶段：人工管理阶段，文件系统阶段和数据库系统阶段。 其中最后一个阶段结构简单，使用方便，逻辑性强，物理性少，在各方面的表现都最好，一直占据数据库领域的主导地位。 9.自然链接是一种特殊的等值连接，它要求两个关系中进行比较的分量必须是相同的属性 组，并且在结果中把重复的属性列去掉。 10.内存又称主存，是CPU能直接寻址的存储空间，由半导体器件制成。内存的特点是存取 速率快。所以微机中访问速度最快的存储器是内存。 11.计算机能直接识别和执行的语言是机器语言，机器语言是用二进制代码表示的计算机能 直接识别和执行的一种机器指令的集合。它是计算机的设计者通过计算机的硬件结构赋予计算机的操作功能。机器语言具有灵活，直接执行和速度快等特点。 12.1MB=1024KB=1024*1024B=220B 13.Internet的四层结构分别是：网络接口层，网络层，传输层和应用层。 14.有序线性表既可以采用顺序存储结构，也可以采用链式存储结构。 15.栈支持子程序调用。栈是一种只能在一端进行插入或删除的线性表。 16.二叉树的基本性质：在任意一棵二叉树中，度为0的叶子结点总是比度为2的结点多一 个。 例如:某二叉树有五个度为2的结点，则该二叉树中的叶子结点数是5+1=6个。 17.冒泡排序与简单插入排序与简单选择排序法在最坏情况下均需要比较n(n-1)/2次，而堆 排序在最坏的情况下需要比较的次数是nlog2n，即在排序方法中，最坏情况下比较次数最少的是堆排序。 18.软件按功能可分为：应用软件，系统软件和支撑软件（或工具软件）。 19.软件测试的目的是为了发现错误而执行程序的过程，并不涉及改正错误。 程序调试的基本步骤有：错误定位，修改设计和代码，以排除错误进行回归测试，防止引进新的错误。程序调试通常称为Debug,即排错。 20.软件测试的基本准则有：所有测试都应追溯到需求，严格执行测试计划，排除测试的随 意性，充分注意测试中的群集现象，程序员应避免检查自己的程序，穷举测试不可能， 第一章数据结构与算法 1.1算法 算法：是指解题方案的准确而完整的描述。 算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。 算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括： （1）可行性； （2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性； （3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义； （4）拥有足够的情报。 算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。 指令系统：一个计算机系统能执行的所有指令的集合。 基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。 算法的控制结构：顺序结构、选择结构、循环结构。 算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。 算法复杂度：算法时间复杂度和算法空间复杂度。 算法时间复杂度是指执行算法所需要的计算工作量。 算法空间复杂度是指执行这个算法所需要的内存空间。 1.2数据结构的基本基本概念 数据结构研究的三个方面： （1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构； （2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构； （3）对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。 数据的逻辑结构包含： （1）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。 数据的存储结构有顺序、链接、索引等。 线性结构条件： （1）有且只有一个根结点； （2）每一个结点最多有一个前件，也最多有一个后件。 非线性结构：不满足线性结构条件的数据结构。 1．3线性表及其顺序存储结构 线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。 在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。 非空线性表的结构特征： （1）且只有一个根结点a1，它无前件； （2）有且只有一个终端结点an，它无后件； （3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。结点个数n称为线性表的长度，当n=0时，称为空表。 线性表的顺序存储结构具有以下两个基本特点： （1）线性表中所有元素的所占的存储空间是连续的； （2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 ai的存储地址为：ADR(ai)=ADR(a1)+(i-1)k,，ADR(a1)为第一个元素的地址，k代表每个元素占的字节数。 顺序表的运算：插入、删除。（详见14--16页） 1．4栈和队列 栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。 栈按照“先进后出”（FILO）或“后进先出”（LIFO）组织数据，栈具有记忆作用。用top表示栈顶位置，用bottom表示栈底。 栈的基本运算：（1）插入元素称为入栈运算；（2）删除元素称为退栈运算；（3）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化。 队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。Rear指针指向队尾，front 指针指向队头。 队列是“先进行出”（FIFO）或“后进后出”（LILO）的线性表。 队列运算包括（1）入队运算：从队尾插入一个元素；（2）退队运算：从队头删除一个元素。 循环队列：s=0表示队列空，s=1且front=rear表示队列满 公共基础补充知识点 公共基础复习方法： 第一：请把10页纸背下来； 第二：把习题册的公共基础题目做好； 第三：结合考前公共基础补充知识复习好；（注意：下划线的一般是选择题目，框起来的一般是填空题目，没有下划线和方框标识的一般也是选择题目） 数据结构与算法 队：。 栈： 线性表 n2=n0-1 栈具有记忆性。如果要存的数据是1 2 3 4 5，栈可以不顺序存储。 我们存放数据的时候，存储空间不一定是连续的，并且各个元素的存储顺序可以是任意的。如：链表。 在线性链表中查找一个元素比在顺序表中查找一个元素要快， 冒泡排序、选择排序、交换排序、堆排序中平均排序次数最快的是 能够用二分查找的是顺序存储的有序线性表。 程序设计基础 1、 程序设计方法和技术的发展经过了结构化程序设计和面向对象设计两个阶段。 2、 当今程序设计的风格是“清晰第一，效率第二”。 3、 程序可以没有输入，但是一定要有输出。 4、 结构化程序设计遵循：自顶向下，逐步求精，模块化，限制使用goto 语句（常考）。 5、 面向对象的基本特点：标志唯一性，分类性，多态性，封装性，模块独立性。尤其重要的是多态性和封装性。没有类比性。 6、 7、 8、 对应类的一个实例。（常考） 9、 10 表 13、 黑盒测试是对软件已经实现的功能是否满足需求进行测试和验证。方法有：等价类划分法，边界值划分法， 错误推测法。 14、 软件测试的四个步骤。自己默写一遍。 15、 程 16、 软件调试方法：强制排错法，回朔法，原因排除法。 17、 软件维护不属于软件生命周期开发阶段的任务。 18、 软件进行了程序调试后还要进行测试。 19、 软件工程的主要思想是：强调在软件开发过程中需要应用工程化的原则。 20、 软件设计中，不属于过程设计工具的是：DFD 图。 21、 结构化分析常见的工具：DFD 图，DD （数据字典），判定树，判定表。 22、 程 23、 软件的开发、运行对计算机系统具有依赖性。 计算机公共基础知识考点 第一章数据结构与算法 1.1 算法 1.算法的基本概念 （1）概念：算法是指一系列解决问题的清晰指令。 （2）4个基本特征：可行性、确定性、有穷性、拥有足够的情报。 （3）两种基本要素：对数据对象的运算与操作、算法的控制结构（运算和操作时间的顺序）。（4）设计的基本方法：列举法、归纳法、递推法、递归法、减半递推技术和回溯法。 2.算法的复杂度 （1）算法的时间复杂度：执行算法所需要的计算工作量。 （2）算法的空间复杂度：执行算法所需的内存空间。 1.2数据结构的基本概念 数据结构线互有关联的数据元素的几何，即数据的组织形式。其中逻辑结构反应数据元素之间逻辑关系；存储结构为数据的逻辑结构在计算机存储空间中的存放形式，有顺序储存、链式储存、索引储存和散列储存四种方式。 数据结构按照各个元素之间前后间关系的复杂程度可以划分为： （1）线性结构：有且只有一个根节点，且每个节点最多有一个直接前驱和一个直接后继的非空数据结构。 （2）非线性结构：不满足线性结构的数据结构。 1.3线性表及其顺序结构性储存 1.线性表的基本概念 线性结构又称线性表，线性表是最简单也是最常用的一种数据结构。 2.线性表的顺序储存结构 ·元素所占的存储空间必须连续。 ·元素在存储空间的位置是按照逻辑顺序存放的。 3.线性表的插入运算 在第i个元素之前插入一个新元素的步骤如下： 步骤一：把原来第n个节点至第i个节点的一次往后移一个元素位置。 步骤二：把新节点放在第i个位置上。 步骤三：修正线性表的节点个数。 在最坏的情况下，即插入元素在第一个位置，线性表中所有元素均需要移动。 4.线性表的删除运算 删除第i个位置的元素的步骤如下： 步骤一：把第i个元素的n-i个元素一次往前移动一个位置； 步骤二：修正线性表的结点个数。 1.4栈和队列 1.栈及其基本运算 （1）基本概念：栈是一种特殊的线性表，其插入原酸与删除运算只在线性表的一端进行，也成为“先进后出”表或“后进先出”表。 ·栈顶：允许插入与删除的一端。 ·栈低：栈顶的另一端。 ·空栈：栈中没有元素的栈。 （2）特点 ·栈顶元素是最后被插入和最早被删除的元素。计算机公共基础教学大纲
中等职业学校公共基础课水平测试计算机测试试卷及答案B
全国计算机二级考试公共基础知识题库365题及答案
计算机二级公共基础知识题库及答案
最全计算机公共基础知识试题汇总
全国计算机等级考试二级-计算机二级公共基础知识点汇总
计算机公共基础部分知识归纳
高校计算机公共基础课实验报告改革探讨
全国计算机二级考试公共基础知识题库
计算机二级公共基础知识高频考点归纳总结
计算机二级考试历年公共基础知识真题
2020年公共基础知识计算机练习题
计算机二级公共基础知识要点总结
计算机公共基础
计算机公共基础知识重点必考
计算机公共基础知识考点
相关主题
文本预览