T11

题意：若3个顶点的无权图G的邻接矩阵用数组存储为{{0, 1, 1},{1, 0, 1},{0, 1, 0}},假定在具体存储中顶点依次为：v1,v2,v3。关于该图，下面的说法哪个是错误的？（C）

A，该图是有向图

B，该图是强连通的

C，该图的入度与出度之差为1

D，该图从v1开始bfs，有多种方式

思路：所有图的入度与出度之差均为0

错误原因：存图时多存了一条边，导致选了A

T12

题意：12.在带尾指针（链表指针clist指向尾结点）的非空循环单链表中每个结点都以next字段的指针指向下一个结点。假定其中已经有了2个以上的结点。下面哪个说法是正确的？（C）

A，如果p指向一个待插入的新节点，在头部插入一个元素的语句序列为p->next=clist;clist->next=p;

B，如果p指向一个待插入的新节点，在尾部插入一个元素的语句序列为p->next=clist;clist->next=p;

C，在头部删除一个节点的语句序列为p=clist->next;clist->next=clist->next->next;delete(p);

D，在尾部删除一个节点的语句序列为p=clist;clist=clist->next;delete(p);

程序阅读1

#include <cmath>
#include <cstdio>
int a1[1001];
int i, j, t, t2, n;
int main() {
    scanf("%d", &n);
    for (i = 2; i <= sqrt(n); i++) {
        if (a1[i] == 0)
        {
            t2 = n / i;
            for (j = 2; j <= t2; j++)
                a1[i * j] = 1;
        }
    }
    t = 0;
    for (i = 2; i <= n; i++)
        if (a1[i] == 0)
        {
            printf("%d", i);
            t++;
            if (t % 10 == 0)
                printf("\n");
        }
    printf("\n");
    return 0;
}

这段程序是质数筛（埃式筛）

程序阅读2

#include  <ctype.h>
#include  <stdio.h>
void expand(char s1[], char s2[])
{
    int i, j, a, b, c;
    j = 0;
    for (i = 0; (c = s1[i]) != '\0'; i++)
        if(c == '-')
        {
            a = s1[i - 1]; b = s1[i + 1];
            if (isalpha(a) && isalpha(b) || isdigit(a) && isdigit(b))
            {
                j--;
                do
                    s2[j++] = a++;
                while (tolower(a) < tolower(s1[i + 1]) && isalpha(a));
            }
            else s2[j++] = c;
        } else s2[j++] = c;
    s2[j] = '\0';
}
int main()
{
    char s1[100], s2[300];
    gets(s1);
    expand(s1, s2);
    printf("%s\n", s2);
}

这个代码是在展开一个字符串，如字符串A-G，它会输出ABCDEFG

程序阅读3

#include<iostream>
#include<cstring>
using namespace std;
const int mm = 1007;
int map[mm][mm];
int n;
int main() {
    cin >> n;
    n--;
    memset(map, 0, sizeof(map));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            map[i][j] = (i + j) % n + 1;
        }
    }
    for (int i = 0; i < n; i++) {
        map[i][n] = map[n][i] = map[i][i];
        map[i][i] = 0;
    }
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            cout << map[i][j] << "";
        }
        cout << endl;
    }
    return 0;
}

生成一个数字矩阵，其行列上数字均为0到n-1，其左上右下对角线均为0，右上左下对角线均为1

完善程序1 求字符的逆序

#include <bits/stdc++.h>
int maxline = 200, kz;
int reverse (char s[] ) {
    int i, j, t;
    for (i = 0, j = strlen(s) - 1; i < j; i++, j--)
    {
        t = s[i];
        s[i] = s[j];
        s[j] = t;
    }
    return (0);
}
int main () {
    char line[100];
    cin >> kz;
    while (kz != -1)
    {
        cin >> line;
        reverse(line);
        cout << line << end1;
        cout << "continue? -1 for end. " << endl;
        cin >> kz;
    }
}

求一个字符串的逆序

完善程序2 棋盘覆盖问题

#include <bits/stdc++.h>
using namespace std;
int board[65][65], tile;
void chessboard(int tr, int tc, int dr, int dc, int size)
{
    int t, s;
    if (size == 1)
        return;
    t = tile++;
    s = size / 2;
    if (dr < tr + s)
        chessboard(tr, tc, dr, dc, s);
    else{
        board[tr + s - 1][tc + s - 1] = t;
        chessboard(tr, tc, tr + s - 1, tc + s - 1, s);
    }
    if (dr < tr + s && dc >= tc + s)
        chessboard(tr, tc + s, dr, dc, s);
    else {
        board[tr + s - 1][tc + s] = t;
        chessboard(tr, tc + s, tr + s - 1, tc + s, s);
    }
    if (dr >= tr + s && dc < tc + s)
        chessboard(tr + s, tc, dr, dc, s);
    else {
        board[tr + s][tc + s - 1] = t;
        chessboard(tr + s, tc, tr + s, tc + s - 1, s);
    }
    if (dr >= tr + s && dc >= tc + s)
        chessboard(tr + s, tc + s, dr, dc, s);
    else {
        board[tr + s][tc + s] = t;
        chessboard(tr + s, tc + s, tr + s, tc + s, s); }
}
void prt1(int b[][65], int n)
{
    int i, j;
    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= n; j++)
            cout << setw(3) << b[i][j];
        cout << endl;
    }
}
void main()
{
    int size, dr, dc;
    cout << "input size(4/8/16/64):" << endl;
    cin >> size;
    cout << "input the position of special block(x,y):" << end1;
    cin >> dr >> dc;
    board[dr][dc] = -1;
    tile++;
    chessboard(1, 1, dr, dc, size);
    prt1(board, size);
}

给定一个棋盘和一个特殊格子，有一种纸片，为L字形（占3格，可旋转），要在棋盘上摆纸片，要求全部铺满，输出最后棋盘样子。运用分治思想，把一个棋盘看作多个，分别求出答案